Array Kombinatorik in PHP

Question

Betrachte folgende Array:

$a = [['x'], ['y', 'z', 'w'], ['m', 'n']]; 

Wie kann daraus folgende Array erzeugen:

$output=[ 
[[x][y][m]], 
[[x][z][n]], 
[[x][w][m]], 
[[x][y][n]], 
[[x][z][m]], 
[[x][w][n]], 
]; 

ich für einen effizienteren Code bin auf der Suche als meine. (Mein aktueller Code wird als Antwort unten dargestellt)

Answer 1

Hier gehen wir. Unter der Annahme:

$array = [['x'], ['y', 'z', 'w'], ['m', 'n']]; 

EDIT: Nach einigen Performance-Tests, schloss ich die Lösung, die ich vor geschrieben ist etwa 300% langsamer als OP Code, sicherlich aufgrund verschachtelten Funktionsaufrufes Stapel. So, hier ist eine verbesserte Version des OP Ansatzes, die rund 40% schneller:

$count  = array_map('count', $array); 
$finalSize = array_product($count); 
$arraySize = count($array); 
$output = array_fill(0, $finalSize, []); 
$i = 0; 
$c = 0; 
for (; $i < $finalSize; $i++) { 
    for ($c = 0; $c < $arraySize; $c++) { 
     $output[$i][] = $array[$c][$i % $count[$c]]; 
    } 
} 

Es ist im Grunde der gleiche Code, aber ich verwenden native Funktionen, wenn möglich, und auch die Schleifen nahm einige Funktionen, die hadn‘ t wird bei jeder Iteration ausgeführt.

Answer 2

<?php 
function array_permutation(array $a) 
{ 
    $count = array_map('count', $a); 
    $finalSize = 1; 

    foreach ($count as $val) { 
     $finalSize *= $val; 
    } 

    $output = []; 

    for ($i = 0; $i < $finalSize; $i++) { 
     $output[$i] = []; 
     for ($c = 0; $c < count($a); $c++) { 
      $index = ($i + $finalSize) % $count[$c]; 
      array_push($output[$i], $a[$c][$index]); 
     } 
    } 
    return $output; 
} 

$a = [['x'], ['y', 'z', 'w'], ['m', 'n']]; 
$output= array_permutation($a); 

Answer 3

"effizienter Code" ist so eine subjektive Sache .... ;-)
Sie könnten Iteratoren anstelle von Arrays verwenden, so dass das vollständige Ergebnis nicht im Speicher gespeichert werden muss. Auf der anderen Seite ist diese Lösung wahrscheinlich viel langsamer.

<?php 
class PermIterator implements Iterator { 
    protected $mi; 
    protected $finalSize, $pos; 

    public function __construct(array $src) { 
     $mi = new MultipleIterator; 
     $finalSize = 1; 
     foreach ($src as $a) { 
      $finalSize *= count($a); 
      $mi->attachIterator(new InfiniteIterator(new ArrayIterator($a))); 
     } 
     $this->mi = $mi; 
     $this->finalSize = $finalSize; 
     $this->pos = 0; 
    } 

    public function current() { return $this->mi->current(); } 
    public function key() { return $this->mi->key(); } 
    public function next() { $this->pos+=1; $this->mi->next(); } 
    public function rewind() { $this->pos = 0; $this->mi->rewind(); } 
    public function valid() { return ($this->pos < $this->finalSize) && $this->mi->valid(); } 
} 


$src = $a = [['x'], ['y', 'z', 'w'], ['m', 'n']]; 
$pi = new PermIterator($src); // <- you can pass this one around instead of the array 
foreach ($pi as $e) { 
    echo join(', ', $e), "\n"; 
} 

druckt

x, y, m 
x, z, n 
x, w, m 
x, y, n 
x, z, m 
x, w, n 

Oder als ein Array (Objekt), in dem Sie jedes Element über eine ganze Zahl

Offset-Zugriff

<?php 
class PermArray implements ArrayAccess { 
    // todo: constraints and error handling - it's just an example 
    protected $source; 
    protected $size; 

    public function __construct($source) { 
     $this->source = $source; 
     $this->size = 1; 
     foreach ($source as $a) { 
      $this->size *= count($a); 
     } 
    } 
    public function count() { return $this->size; } 

    public function offsetExists($offset) { return is_int($offset) && $offset < $this->size; } 
    public function offsetGet($offset) { 
     $rv = array(); 
     for ($c = 0; $c < count($this->source); $c++) { 
      $index = ($offset + $this->size) % count($this->source[$c]); 
      $rv[] = $this->source[$c][$index]; 
     } 
     return $rv; 
    } 

    public function offsetSet($offset, $value){} 
    public function offsetUnset($offset){} 
} 

$pa = new PermArray([['x'], ['y', 'z', 'w'], ['m', 'n']]); 
$cnt = $pa->count(); 
for($i=0; $i<$cnt; $i++) { 
    echo join(', ', $pa[$i]), "\n"; 
} 

Answer 4

Es scheint, als ob keine der Antworten, einschließlich der akzeptiert man, wird funktionieren, wenn es zwei Arrays gleicher Länge gibt. Ich habe die akzeptierte Antwort persönlich getestet und festgestellt, dass dies der Fall ist, und nach den Kommentaren zu den anderen beiden haben sie das gleiche Problem.

Ich musste diesen Algorithmus vor kurzem implementieren, also werde ich meine Lösung posten. Diese Lösung wurde für die Verwendung mit assoziativen Arrays entwickelt und unterstützt auch Gruppen von Spalten, die in der Ausgabe zusammen gruppiert und nicht gegeneinander vertauscht werden. Dies ist nützlich, wenn eine der Spalten verwandte Informationen enthält. Wenn Sie diese Funktionen nicht benötigen, sollte es ziemlich trivial sein, diesen Algorithmus so zu modifizieren, dass er Ihren Anforderungen entspricht.

// the input column sets to be permuted 
$column_sets = [ 
    [ //set 1 
     ['Column 1' => 'c1v1'] 
    ], 
    [ //set 2 
     ['column 2' => 'c2v1', 'Column 3' => 'c3v1'], 
     ['column 2' => 'c2v2', 'Column 3' => 'c3v2'], 
    ], 
    [ //set 3 
     ['Column 4' => 'c4v1', 'Column 5' => 'c5v1'], 
     ['Column 4' => 'c4v2', 'Column 5' => 'c5v2'], 
    ], 
    [ //set 4 
     ['Column 6' => 'c6v1', 'Column 7' => 'c7v1'], 
     ['Column 6' => 'c6v2', 'Column 7' => 'c7v2'], 
     ['Column 6' => 'c6v3', 'Column 7' => 'c7v3'], 
    ], 
    [ //set 5 
     ['Column 8' => 'c8v1', 'Column 9' => 'c9v1'], 
     ['Column 8' => 'c8v2', 'Column 9' => 'c9v2'], 
     ['Column 8' => 'c8v3', 'Column 9' => 'c9v3'], 
    ], 
]; 

// copy the first set into the output to start 
$output_rows = $column_sets[0]; 

foreach ($column_sets as $column_set) { 
    // save the current state of the rows for use within this loop 
    $current_output = $output_rows; 

    // calculate the number of permutations necessary to combine the output rows with the current column set 
    $permutations = count($output_rows) * count($column_set); 
    for ($permutation=0; $permutation < $permutations; $permutation++) { 

     // if the current permutation index is grater than the number of rows in the output, 
     // then copy a row from the pre-permutation output rows, repeating as necessary 
     if ($permutation > count($output_rows) - 1) { 
      $output_rows[] = $current_output[$permutation % count($current_output)]; 
     } 

     // copy the columns from the column set 
     foreach ($column_set[0] as $key => $value) { 
      $output_rows[$permutation][$key] = $column_set[intval($permutation/count($current_output)) % count($column_set)][$key]; 
     } 
    } 
} 


echo "After Permutaion:\n"; 
echo implode("\t", array_keys($output_rows[0])) . PHP_EOL; 
foreach ($output_rows as $row) { 
    echo implode("\t", array_values($row)) . PHP_EOL; 
} 

Answer 5

[x][y][z] 
[x][z][y] 
[y][x][z] 
[y][z][x] 
[z][x][y] 
[z][y][x] 

denke ich, Ihr Problem nicht Permutation ist, sondern Kombinatorik, denn wenn Permutation Code wird ausgegeben, was oben geschrieben wird das Array von if gegeben {x, y, z} die Formel für Permutation ist, dass n !/(n-1)! in diesem Fall ist es 6. so sechs Permutationen.