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.

• scrowler: I find your example output a bit confusing - can you provide a full example output?
• Rizier123: I'm also a bit confused with your expected output. Please provide all combinations which you expect for the example data. As I see it now you just want to pick a number from each subArray, but don't want duplicate values. But you also still want each combination be the length of all subArrays. You also seem to use NULL as "filler" to get to your combination length. So you consider it as it would be a value in each subArray?! So would be a combination like: [1, 2, NULL, NULL] possible if the last two subArrays only contain 1 and 2's?
• Rizier123: And if you have 3 subArrays, is [NULL, NULL, NULL] a possible combination? Or is "NULL" just a filler? Also as you show the keys explicit in your output, do you want to use the keys of the subArrays? Or does it just happen to be the same ones?
• simPod: @Rizier123 [NULL, NULL, NULL] is not a possible combination. Also, [1, 2, NULL, NULL] is not as it has 4 elements. Basically, NULL appears only when every element of current subarray has been already used as in this example: [0 => 1,1 => 3,2 => null]. There's [1,3] as a third subarray. However 1 and 3 has been picked from previous subarrays so it cannot be picked again.
• Rizier123: @simPod Okay so it is just a filler to get the expected length for the combination. But just to make sure: If you have 4 subArrays then [1, 2, NULL, NULL] would be possible if the last two subArrays only contain 1 or 2? + Are they keys from the output taken from the input array or just enumerated?

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

• Rizier123: [1,2,3] and [2,3,1] are the same combination. Same as [2,4,1] and [4,2,1].
• Stephen Fulton: @Rizier123, simPod shows [1,2,3] and [2,3,1] as correct results. I took that to mean that order is important. Which would make those different combinations.
• Rizier123: You are right, I didn't looked good enough, but then he wants the permutations and not combinations, I will ask in the comments.
• Rizier123: You were correct. OP wants the permutations. But then there will be a lot more than your code outputs.
• Stephen Fulton: I'm sorry but there is no possible way to calculate that many items. Even on a supercomputer it would take more time than the universe has been in existence. (not an exaggeration).

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

• simPod: Thank you for your help. I tried to input [[ 1, 2], [2, 3, 4 ], [ 1, 3 ]] so it should also return this combination [null, 2, 1] but it does not :(
• Rizier123: While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion. Please also try not to crowd your code with explanatory comments, this reduces the readability of both the code and the explanations!
• Rizier123: As it seems OP wants to get all permutations and not only the combinations .