By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,258 Members | 1,714 Online
Bytes IT Community
+ Ask a Question
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

zorgi
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
  1. $my_array = array(
  2.             "b" => array("t", "p"), 
  3.             "t" => array("p", "b"), 
  4.             "d" => array("b", "t"), 
  5.             "p" => array("b", "d", "n"), 
  6.             "n" => array("d", "b")
  7.         );
  8.  
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

✓ answered by zorgi

.......... 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.  

Share this Question
Share on Google+
15 Replies


code green
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

zorgi
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

code green
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
  1. foreach($my_array as $key=>$arrayin)
  2. {
  3.     foreach($arrayin as $keyin=>$valuein)
  4.     {
  5.         if(in_array($keyin,$my_array)
  6.         {
  7.             //Do something, not sure what. My head hurts
  8.         }
  9.     }
  10.  
Might have that the wrong way around but you get the idea
May 13 '10 #4

zorgi
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

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

zorgi
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

code green
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
  1. foreach($my_array as $key=>$arrayin)  
  2. {  
  3.     foreach($arrayin as $valuein)  
  4.     {  
  5.         if(isset($my_array[$valuein])  
  6.         {  
  7.             echo 'Yehey I've found a circle;        }  
  8.     }  
  9.  
May 13 '10 #8

zorgi
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

code green
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

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

zorgi
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

code green
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

zorgi
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

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

zorgi
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
  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.  
May 17 '10 #16

Post your reply

Sign in to post your reply or Sign up for a free account.