array permutations with a condition

Question

This must be simple, but my brain is fried by the end of the day.. Please help:

<?php

    $arr = array(
        array(1, 2, 3),
        array(10, 20, 30),
        array(100, 200, 300),
    );

?>

I need all possible permuations of the inner arrays with the only exception that each element of every inner array can only be used once per each permutation. E.g.:

GOOD:

1-10-100
1-100-10
200-1-10

BAD:

1-2-3
30-20-200

The original layout can be changed.

Now that you have a few answers, maybe you should mark one as answered? — Mic1780
– Mic1780, Commented Mar 8, 2013 at 1:44
Mic, thank you for the advice. I will definitely consider it.. Or I might set a bounty instead.. — Geo
– Geo, Commented Mar 8, 2013 at 15:01

Sammitch · Accepted Answer · 2013-03-05 22:47:07Z

2

This will work for any number of arrays:

<?php

$arr = array(
    array(1, 2, 3),
    array(10, 20, 30),
    array(100, 200, 300),
    array(1000, 2000, 3000)
);

function permute($a, $b) {
    $perms = array();
    foreach($a as $va) {
        foreach($b as $vb) {
            $perms[] = sprintf('%s-%s', $va, $vb);
        }
    }
    return $perms;
}

$i=2;
$perms = permute($arr[0], $arr[1]);
while($i<count($arr)) {
    $perms = permute($perms, $arr[$i++]);
}

print_r($perms);

answered Mar 5, 2013 at 22:47

Sammitch

32.5k7 gold badges58 silver badges92 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Geo Over a year ago

This is very good, but doesn't do all. Combinations like 1000-1-10-100 or 2000-1-10-100 are missing

rdt.exe · Accepted Answer · 2013-03-10 23:48:41Z

This should work for any number of arrays:

<?php
$arr = array(
    array(1, 2, 3),
    array(10, 20, 30),
    array(100, 200, 300),
);
print_r(foo(array(), $arr));

function foo($arr1 = array(), $arr2 = array()) {
    $perm_arr = array();

    // case 1: empty array vs outer array
    // eg: array() vs array(array(1, 2, 3), array(10, 20, 30), array(100, 200, 300))
    // recursively reduce the size of outer array via case 2
    if(empty($arr1) && (isset($arr2[0]) && is_array($arr2[0]))) {
        $arr_top = array();
        $arr_bot = $arr2;

        // get possible arrangements for further reduction
        // eg:
        // array(1, 2, 3) vs array(array(10, 20, 30), array(100, 200, 300)),
        // array(10, 20, 30) vs array(array(1, 2, 3), array(100, 200, 300)),
        // array(100, 200, 300) vs array(array(1, 2, 3), array(10, 20, 30)),
        // ...
        while(0 < count($arr_bot)) {
            $arr = array_shift($arr_bot);
            $arr_edge = array_merge($arr_top, $arr_bot);
            $foo_arr_edge = foo($arr, $arr_edge);

            // append permutations of reduced array
            foreach($foo_arr_edge as $e_edge) {
                $perm_arr[] = $e_edge;
            }

            $arr_top[] = $arr;
        }
    }
    // case 2: inner array vs outer array
    // eg: array(1, 2, 3) vs array(array(10, 20, 30), array(100, 200, 300))
    // reduce the size of outer array until it reaches the base case
    else if(isset($arr1[0]) && (isset($arr2[0]) && is_array($arr2[0]))) {
        $foo_arr2 = array();

        $n_arr2 = count($arr2);
        // if the size of outer array is greater than 2 then reduce it until the size is 2
        if(2 < $n_arr2) {
            $arr_top = array();
            $arr_bot = $arr2;

            // get possible arrangements for further reduction
            // eg:
            // array(1, 2, 3) vs array(10, 20, 30),
            // array(1, 2, 3) vs array(100, 200, 300),
            // array(10, 20, 30) vs array(100, 200, 300),
            // ...
            while(0 < count($arr_bot)) {
                $arr = array_shift($arr_bot);
                $arr_edge = array_merge($arr_top, $arr_bot);
                $foo_arr_edge = foo($arr, $arr_edge);

                foreach($foo_arr_edge as $e_edge) {
                    $foo_arr2[] = $e_edge;
                }

                $arr_top[] = $arr;
            }
        }
        // if the size of outer array is 2 then get the permutations of its elements via the base case
        else if(2 == $n_arr2) {
            $foo_arr2 = foo($arr2[0], $arr2[1]);
        }

        // generate permutations from reduced array
        foreach($arr1 as $e1) {
            foreach($foo_arr2 as $e2) {
                $perm = $e1 .'-'. $e2;
                $perm_arr[] = $perm;
            }
        }
    }
    // base case: inner array vs inner array
    // eg: array(1, 2, 3) vs array(10, 20, 30)
    // generate permutations of two inner arrays
    else if(isset($arr1[0]) && (isset($arr2[0]) && !is_array($arr2[0]))) {
        foreach($arr1 as $e1) {
            foreach($arr2 as $e2) {
                $perm = $e1 .'-'. $e2;
                $perm_arr[] = $perm;
            }
        }
        foreach($arr2 as $e2) {
            foreach($arr1 as $e1) {
                $perm = $e2 .'-'. $e1;
                $perm_arr[] = $perm;
            }
        }
    }

    return $perm_arr;
}
?>

This one seems to be working excellent! But the solution is sooo large??
Okay, I will probably be accepting this answer, however it needs enhancements: either comments explaining what each part does and why it is necessary or a decent refactoring that will make the code more concise. (or both)

Mic1780 · Accepted Answer · 2013-03-05 22:18:33Z

0

I believe this is the answer you are looking for:

<?php

$nL =   '
';
$arr = array(
        array(1, 2, 3),
        array(10, 20, 30),
        array(100, 200, 300),
    );

foreach ($arr[0] as $key => $val1) {
    foreach ($arr[1] as $val2) {
        foreach ($arr[2] as $val3) {
            echo $val1 . '-' . $val2 . '-' . $val3 . $nL;
        }
    }
}

foreach ($arr[0] as $key => $val1) {
    foreach ($arr[2] as $val2) {
        foreach ($arr[1] as $val3) {
            echo $val1 . '-' . $val2 . '-' . $val3 . $nL;
        }
    }
}

foreach ($arr[1] as $key => $val1) {
    foreach ($arr[0] as $val2) {
        foreach ($arr[2] as $val3) {
            echo $val1 . '-' . $val2 . '-' . $val3 . $nL;
        }
    }
}

foreach ($arr[1] as $key => $val1) {
    foreach ($arr[2] as $val2) {
        foreach ($arr[0] as $val3) {
            echo $val1 . '-' . $val2 . '-' . $val3 . $nL;
        }
    }
}

foreach ($arr[2] as $key => $val1) {
    foreach ($arr[0] as $val2) {
        foreach ($arr[1] as $val3) {
            echo $val1 . '-' . $val2 . '-' . $val3 . $nL;
        }
    }
}

foreach ($arr[2] as $key => $val1) {
    foreach ($arr[1] as $val2) {
        foreach ($arr[0] as $val3) {
            echo $val1 . '-' . $val2 . '-' . $val3 . $nL;
        }
    }
}

echo    'finished';
?>

Enjoy. =)

answered Mar 5, 2013 at 22:18

Mic1780

1,80410 silver badges23 bronze badges

4 Comments

mellamokb Over a year ago

+1 Gets the job done. However, won't work if the number of arrays changes.

Arjan Over a year ago

Your $nL should be defined as PHP_EOL to make sure you get the correct EndOfLine character for the current platform.

Mic1780 Over a year ago

Sorry. I am used to using $nL as a newLine concatination since it moves all codes to the next time.

Mic1780 Over a year ago

Im sorry for your reason for the votedown. Given in your example you provided three arrays so i created a solution for three arrays. Just because I did not make it for a different number of arrays does not mean my answer is wrong. Next time you ask a question be specific in it and do not downvote people because YOU don't like the way they do it when you are looking for a solution.

Collectives™ on Stack Overflow

array permutations with a condition

3 Answers 3

1 Comment

3 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

3 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related