陣列組合數學在PHP

Question

考慮跟進陣列：

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

如何從它產生以下數組：

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

我正在尋找一個更高效的代碼比我的。 （我現在的代碼作爲下面的答案）

Answer 1

在這裏，我們走吧。假設：

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

編輯：後一些性能測試，我總結我以前張貼的解決方案比OP的代碼慢約300％，無疑因嵌套函數調用堆棧。因此，這裏是OP的做法，這是更快左右40％的改進版本：

$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]]; 
    } 
} 

它基本上是相同的代碼，但我用本地函數時，可能並還拿出了循環的一些功能，hadn」 t在每次迭代中執行。

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

「更高效的代碼」就是這樣一個主觀的東西.... ;-)
你可以使用迭代器而不是數組，因此完整的結果不需要存儲在內存中。另一方面，這種解決方案最可能慢得多。

<?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"; 
} 

打印

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

或者作爲陣列（對象）在這裏可以通過一個整數訪問每個元件偏移

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

看來好像沒有一個答案，包括接受一個，如果有兩個相同長度的數組，將會工作。我親自測試了接受的答案，發現情況是這樣，從另外兩個人的評論來看，他們有同樣的問題。

我不得不最近實施這個算法，所以我會發布我的解決方案。此解決方案旨在與關聯數組一起使用，並且還支持將在輸出中組合在一起並且不會相互排列的一組列。如果任何列包含相關信息，這很有用。如果您不需要這些功能，修改此算法以支持您的需求應該相當簡單。

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

我認爲你的問題是不是置換，而是組合學，因爲如果排列你的代碼是什麼上面，如果給定的數組書面輸出{X，Y，Z}用於置換的公式是n個！/（N-1）！在這種情況下，它是六個排列組合。