Circles and arrays

[zorgi]

Hi Guys

I have this algorithm problem to share with you: :)

Imagine you have two dimensional array like this:

$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

[code green]

Is this for a game? I think in_array() will be very useful.
But you will hve to hand loop the outer array

[zorgi]

@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

[code green]

Could you elaborate on your "hand loop the outer array" approach.

I'll have go

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

[zorgi]

@code green
hahahaha

"//Do something, not sure what. My head hurts" is exactly where I loose it :)

Thanx :)))

[code green]

Hmm I think that is wrong

foreach($my_array as $key=>$arrayin) 
{ 
    foreach($arrayin as $valuein) 
    { 
        if(in_array($valuein,$my_array) 
        { 
            echo 'Yehey I've found a circle;        } 
    } 
 

[zorgi]

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.

[code green]

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

foreach($my_array as $key=>$arrayin)  
{  
    foreach($arrayin as $valuein)  
    {  
        if(isset($my_array[$valuein])  
        {  
            echo 'Yehey I've found a circle;        }  
    }  
 

[zorgi]

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

[code green]

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?

[zorgi]

If necessary we can use database no probs.

[zorgi]

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.

[code green]

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.

[zorgi]

I still think solution is somewhere with recursive functions however much I dont like them. Thanks for trying.

[zorgi]

Maybe this one should be moved to Algorithms too?!

[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:

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);
        }            
    }
}