alle möglichen Permutationen ohne Wiederholung der Wert

Question

Lassen Sie uns sagen, ich habe diesen Satz von Arrays als Eingang:

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

Ich möchte alle Permutationen finden mögliche Auswahl eines Wertes von jedem Array. Dieser Wert würde im Endergebnis eindeutig sein und wird daher nicht wiederholt. Zum Beispiel kann ich 1 nicht zweimal im Ergebnis haben.

Die Anzahl der Arrays am Eingang entspricht der Anzahl der Arrays am Ausgang.

Beispiele für Kombinationen gesucht (Schlüssel => Wert):

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

Falsche Ergebnisse

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

oder

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

---

Ich möchte mit PHP alle möglichen Permutationen bekommen. Wie kann ich das machen?

Ich habe einen echten Datensatz angehängt http://pastebin.com/U6Hyawm4 Allerdings habe ich keine Ahnung, wie viele Permutationen es gibt.

Answer 1

Hier ist eine nicht-rekursive Version, die ebenfalls

/** 
* 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 
    } 
} 

Das resultierende Array optimiert ist:

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

Hier ist eine ineffiziente 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); 

Ausgänge:

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 
     ) 

)