459,258 Members | 1,714 Online Need help? Post your question and get tips & solutions from a community of 459,258 IT Pros & Developers. It's quick & easy.

# Circles and arrays

 Expert 100+ P: 431 Hi Guys I have this algorithm problem to share with you: :) Imagine you have two dimensional array like this: Expand|Select|Wrap|Line Numbers \$my_array = array(             "b" => array("t", "p"),              "t" => array("p", "b"),              "d" => array("b", "t"),              "p" => array("b", "d", "n"),              "n" => array("d", "b")         );   I need algorithm/function that can find all the circles within this two dimensional array. Simplest circle from this example above would be b - t - b Where do I see circle? Well its simple really "b" element of \$my_array contains "t" and "t" element of \$my_array contains "b" so we are back at the starting point. Lets see another bit more complex circle: b - p - d - b "b" contains "p" "p" contains "d" "d" contains "b" \$my_array is dynamically created and the only rule is that its elements (arrays) can not contain its index. What that means is that this element "b" => array("t", "p", "b") can not happen cos "b" element can not contain "b". I hope that I managed to explain problem well and appreciate any input. If something is unclear please ask I'll try to explain. Thanx May 13 '10 #1

.......... And after a while and some help from jkmyoung http://bytes.com/topic/algorithms/an...ree-flattening here is recursive function that does the business:

Expand|Select|Wrap|Line Numbers
1. foreach(\$a as \$key => \$arr){
2.     getClosedList(\$key, \$a);
3. }
4.
5. function getClosedList(\$element, \$mix, \$main_key = NULL, \$main_array = NULL, \$array = array()){
6.     if((end(\$array) == \$main_key)&&(\$main_key != NULL)){
7.         var_dump(\$array);
8.         return;
9.     }
10.     if(!\$main_key){
11.         \$main_key = \$element;
12.         \$main_array = \$mix[\$main_key];
13.     }
14.     unset(\$mix[\$element]);
15.     foreach(\$mix as \$firma_key => \$array_duga){
16.         \$a = \$array;
17.         \$a[] = \$firma_key;
18.         if((in_array(\$firma_key, \$main_array))&&(in_array(\$element, \$array_duga))){
19.             \$a[] = \$main_key;
20.             getClosedList(\$firma_key, \$mix, \$main_key, \$main_array, \$a);
21.         }elseif(in_array(\$element, \$array_duga)){
22.             getClosedList(\$firma_key, \$mix, \$main_key, \$main_array, \$a);
23.         }
24.     }
25. }
26.

15 Replies

 Expert 100+ P: 1,726 Is this for a game? I think in_array() will be very useful. But you will hve to hand loop the outer array May 13 '10 #2

 Expert 100+ P: 431 @code green Thanks for reply Yes in_array() will be useful I am sure, but my problem is not in using manual :) Its more of an algorithm issue. Could you elaborate on your "hand loop the outer array" approach. I would be very grateful. Thanx Again May 13 '10 #3

 Expert 100+ P: 1,726 Could you elaborate on your "hand loop the outer array" approach. I'll have go Expand|Select|Wrap|Line Numbers foreach(\$my_array as \$key=>\$arrayin) {     foreach(\$arrayin as \$keyin=>\$valuein)     {         if(in_array(\$keyin,\$my_array)         {             //Do something, not sure what. My head hurts         }     }   Might have that the wrong way around but you get the idea May 13 '10 #4

 Expert 100+ P: 431 @code green hahahaha "//Do something, not sure what. My head hurts" is exactly where I loose it :) Thanx :))) May 13 '10 #5

 Expert 100+ P: 1,726 Hmm I think that is wrong Expand|Select|Wrap|Line Numbers foreach(\$my_array as \$key=>\$arrayin)  {      foreach(\$arrayin as \$valuein)      {          if(in_array(\$valuein,\$my_array)          {              echo 'Yehey I've found a circle;        }      }    May 13 '10 #6

 Expert 100+ P: 431 Hm I just tested it for the example above and it didn't say "'Yehey Ive found a circle'" at all. Its more complex than it looks at first glance. I think it has to be some sort of recursive function but its very confusing. May 13 '10 #7

 Expert 100+ P: 1,726 I doubt a recursive loop is needed. I've still got it wrong. Replace the in_array() with array_key_exists() or whatever it is. We are trying to match the 'keys' in \$my_array, not the values which are arrays again. Could even use Expand|Select|Wrap|Line Numbers foreach(\$my_array as \$key=>\$arrayin)   {       foreach(\$arrayin as \$valuein)       {           if(isset(\$my_array[\$valuein])           {               echo 'Yehey I've found a circle;        }       }     May 13 '10 #8

 Expert 100+ P: 431 Hmm I can see how this can work for simple circles like "b - t - b" but you can not find circles like "b - p - d - b" using this approach. Maybe I'm missing something in your approach but if you would echo actual circle instead of 'Yehey I've found a circle' you would have only current outer and current inner array to do so and circles may be made from unlimited number of arrays or am I missing something???? May 13 '10 #9

 Expert 100+ P: 1,726 I see your point. There is no limit to the size of the chain. So we don't know how deep to nest the loops. In fact every single permutation has to be mapped. Can we make use of database tables somehow? May 13 '10 #10

 Expert 100+ P: 431 If necessary we can use database no probs. May 13 '10 #11

 Expert 100+ P: 431 I was considering to find all permutations and than just pick those that complete the circle. However if you have just 10 elements in array you have 10! permutations and its very likely that number much higher than 1000 so imagine 1000! that would take forever to compute. May 13 '10 #12

 Expert 100+ P: 1,726 OK, this is an idea. Just concentrating on the 2-deep "b - t - b" run through all the arrays building another set of arrays that define what each array can possibly map to. ie \$b array via 't' and 'p' can map to p,b,d,n so becomes \$b(p,b,d,n). And then loop through the new map arrays and create more arrays that map the maps to the maps. \$bp array for ex The thing is, whatever the solution there has to be a cut-off point somewhere or you could search going round in circles(pun) forever. A maximum chain length needs to be calculated based on what you start with. May 13 '10 #13

 Expert 100+ P: 431 I still think solution is somewhere with recursive functions however much I dont like them. Thanks for trying. May 13 '10 #14

 Expert 100+ P: 431 Maybe this one should be moved to Algorithms too?! May 14 '10 #15

 Expert 100+ P: 431 .......... And after a while and some help from jkmyoung http://bytes.com/topic/algorithms/an...ree-flattening here is recursive function that does the business: Expand|Select|Wrap|Line Numbers foreach(\$a as \$key => \$arr){     getClosedList(\$key, \$a);     }   function getClosedList(\$element, \$mix, \$main_key = NULL, \$main_array = NULL, \$array = array()){         if((end(\$array) == \$main_key)&&(\$main_key != NULL)){         var_dump(\$array);         return;     }     if(!\$main_key){         \$main_key = \$element;         \$main_array = \$mix[\$main_key];     }         unset(\$mix[\$element]);     foreach(\$mix as \$firma_key => \$array_duga){         \$a = \$array;         \$a[] = \$firma_key;         if((in_array(\$firma_key, \$main_array))&&(in_array(\$element, \$array_duga))){                         \$a[] = \$main_key;             getClosedList(\$firma_key, \$mix, \$main_key, \$main_array, \$a);                     }elseif(in_array(\$element, \$array_duga)){                                     getClosedList(\$firma_key, \$mix, \$main_key, \$main_array, \$a);         }                 } }   May 17 '10 #16 