11

考虑以下数组：

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

我正在寻找比我的更有效的代码。（我当前的代码在下面作为答案提供）

4

5 回答 5

9

开始了。假设：

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

它基本上是相同的代码，但我尽可能使用本机函数，并且还取出了循环中一些不必在每次迭代中执行的功能。

于 2012-11-23T10:05:29.677 回答
6

“更高效的代码”是一件很主观的事情.... ;-)
您可以使用迭代器而不是数组，因此不必将完整的结果存储在内存中。另一方面，这种解决方案很可能要慢得多。

<?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";
}
于 2012-11-23T10:24:05.780 回答
0 
<?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);
于 2012-11-23T09:13:32.030 回答
0

如果有两个长度相同的数组，似乎所有答案（包括接受的答案）都不起作用。我亲自测试了接受的答案，发现情况确实如此，从其他两个的评论来看，他们有同样的问题。

我最近不得不实现这个算法，所以我会发布我的解决方案。此解决方案旨在与关联数组一起使用，并且还支持将在输出中组合在一起且不会相互排列的列集；如果任何列包含相关信息，这将很有用。如果您不需要这些功能，那么修改此算法以支持您的需求应该是相当简单的。

// 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;
}
于 2015-06-29T17:32:46.117 回答
-1 
[x][y][z]
[x][z][y]
[y][x][z]
[y][z][x]
[z][x][y]
[z][y][x]

我认为你的问题不是排列，而是组合，因为如果排列你的代码将输出上面写的内容，如果给定 {x,y,z} 的数组，排列的公式是 n!/(n-1)! 在这种情况下，它是 6。所以六个排列。

于 2017-03-16T00:56:10.447 回答