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

これは基本的に同じコードですが、可能な場合はネイティブ関数を使用し、各反復で実行する必要のないループ機能もいくつか削除しました。

Answer 2

「より効率的なコード」は主観的なものです.... ;-)
配列の代わりにイテレータを使用できるため、完全な結果をメモリに保存する必要はありません。一方、このソリューションはおそらくはるかに遅くなります。

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

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