Find all possible permutations without repeating the value

Question

Let's say I have this set of arrays as input:

[
 0 => [1,2,4,5],
 1 => [2,3,4],
 2 => [1,3],
]

I would like to find all permutations possible selecting one value from each array. That value would be unique in the final result, so it won't repeat. For example, I can't have 1 twice in the result.

The count of arrays on input is the same as count of arrays on output.

Examples of combinations wanted (key=>value):

[0 => 1,1 => 2,2 => 3]
[0 => 2,1 => 3,2 => 1]
[0 => 5,1 => 2,2 => 1]
[0 => 1,1 => 3,2 => null]

Wrong results

[0 => 1,1 => 2,2 => 1]

or

[0 => 2,1 => 2,2 => 3]

---

I would like to get set of all possible permutations using PHP. How can I do that?

I have attached real data set http://pastebin.com/U6Hyawm4 However, I have no idea how many permutations there may be.

Answer 1

Here's a non-recursive version that's also optimized

/**
 * Generates all the possible unique N-tuples from an array of N arrays of integers
 *
 * @param array $input
 * @return array
 */
function generateCombinations(array &$input) {
    // since the example results included [1, 3, null] I have assumed that
    // null is a possible value of each set.
    $sets = [];
    foreach($input as $set) {
        if(!in_array(null, $set)) {
            $set[] = null;
        }
        $sets[] = $set;
    }

    // by working on the iterators of each array this loop
    // linearizes the entire set of possible combinations
    // and iterates it (skipping as many as it can).
    $output = [];
    $setCount = count($sets);
    while(current($sets[0]) !== false) {
        $testCombo = [];
        for($setIdx = 0; $setIdx < $setCount; $setIdx++) {
            if(!in_array(current($sets[$setIdx]), $testCombo)) {
                $testCombo[] = current($sets[$setIdx]);
            }
            else {
                // when a combination is thrown out as duplicate
                // iterate to skip any other combo's that would also
                // contain that duplicate
                iterateSets($sets, $setIdx);
                break;
            }
        }
        // if there were no duplicates add it to the output and iterate
        if(count($testCombo) == $setCount) {
            $output[] = $testCombo;
            iterateSets($sets, $setCount - 1);
        }
    }
    return $output;
}

/**
 * Iterates to the next potentially valid combination. I think of
 * this like doing long-hand addition. Add 1 and carry is akin to
 * next and reset.
 *
 * @param array $sets
 * @param $index
 */
function iterateSets(array &$sets, $index) {
    // reset iterators of all sets past the current one to skip
    // combos that cannot be valid
    for($i = $index + 1, $ic = count($sets); $i < $ic; $i++) {
        reset($sets[$i]);
    }
    // always move one on current set
    next($sets[$index]);
    while($index > 0 && current($sets[$index]) === false) {
        // wrap if current set is at the end
        reset($sets[$index]);
        $index--;
        // move one for the preceding set
        next($sets[$index]);
        // then repeat
    }
}

The resulting array is:

[
    [1,2,3]
    [1,2,null]
    [1,3,null]
    [1,4,3]
    [1,4,null]
    [1,null,3]
    [2,3,1]
    [2,3,null]
    [2,4,1]
    [2,4,3]
    [2,4,null]
    [2,null,1]
    [2,null,3]
    [4,2,1]
    [4,2,3]
    [4,2,null]
    [4,3,1]
    [4,3,null]
    [4,null,1]
    [4,null,3]
    [5,2,1]
    [5,2,3]
    [5,2,null]
    [5,3,1]
    [5,3,null]
    [5,4,1]
    [5,4,3]
    [5,4,null]
    [5,null,1]
    [5,null,3]
    [null,2,1]
    [null,2,3]
    [null,3,1]
    [null,4,1]
    [null,4,3]
]

Answer 2

Here's an inefficient version:

$input = array(
    [1,2,4,5],
    [2,3,4],
    [1,3]
);

function appendUnique($subs, $i) {
    global $input;
    if ($i == count($input)) {
        return $subs;
    }

    $output = array();
    foreach ($subs as $sub) {
        foreach ($input[$i] as $v) {
            $new_sub = array_values($sub);
            if (in_array($v, $sub)) {
                $new_sub[] = null;
            } else {
                $new_sub[] = $v;
            }
            $output[] = $new_sub;
        }
    }
    return appendUnique($output, $i+1);
}

$output = appendUnique([[]], 0);
$output_json = array();
foreach ($output as $row) {
    $output_json[] = json_encode($row);
}
$output_json = array_unique($output_json);
$deduped = array();
foreach ($output_json as $json) {
    $deduped[] = json_decode($json);
}
print_r($deduped);

outputs:

Array
(
    [0] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 
        )

    [1] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 3
        )

    [2] => Array
        (
            [0] => 1
            [1] => 3
            [2] => 
        )

    [3] => Array
        (
            [0] => 1
            [1] => 4
            [2] => 
        )

    [4] => Array
        (
            [0] => 1
            [1] => 4
            [2] => 3
        )

    [5] => Array
        (
            [0] => 2
            [1] => 
            [2] => 1
        )

    [6] => Array
        (
            [0] => 2
            [1] => 
            [2] => 3
        )

    [7] => Array
        (
            [0] => 2
            [1] => 3
            [2] => 1
        )

    [8] => Array
        (
            [0] => 2
            [1] => 3
            [2] => 
        )

    [9] => Array
        (
            [0] => 2
            [1] => 4
            [2] => 1
        )

    [10] => Array
        (
            [0] => 2
            [1] => 4
            [2] => 3
        )

    [11] => Array
        (
            [0] => 4
            [1] => 2
            [2] => 1
        )

    [12] => Array
        (
            [0] => 4
            [1] => 2
            [2] => 3
        )

    [13] => Array
        (
            [0] => 4
            [1] => 3
            [2] => 1
        )

    [14] => Array
        (
            [0] => 4
            [1] => 3
            [2] => 
        )

    [15] => Array
        (
            [0] => 4
            [1] => 
            [2] => 1
        )

    [16] => Array
        (
            [0] => 4
            [1] => 
            [2] => 3
        )

    [17] => Array
        (
            [0] => 5
            [1] => 2
            [2] => 1
        )

    [18] => Array
        (
            [0] => 5
            [1] => 2
            [2] => 3
        )

    [19] => Array
        (
            [0] => 5
            [1] => 3
            [2] => 1
        )

    [20] => Array
        (
            [0] => 5
            [1] => 3
            [2] => 
        )

    [21] => Array
        (
            [0] => 5
            [1] => 4
            [2] => 1
        )

    [22] => Array
        (
            [0] => 5
            [1] => 4
            [2] => 3
        )

)