10

我只想找出更好的方法来做到这一点：

$array = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l')
);

目标是打印如下内容：

a e h
a e i
a e j
a e k
a e l

a f h
a f i
a f j
a f k
a f l

a g h
a g i
a g j
a g k
a g l

b然后对and做同样的事情c。

目前，我正在使用以下代码：

foreach ($array[0] as $val1) {
    foreach ($array[1] as $val2) {
        foreach ($array[2] as $val3) {
            echo "$val1  $val2  $val3 \n";
        }
        echo "--------\n";
    }
}

我还尝试动态创建上述代码并使用 eval 执行它：

$eval         = '
     $data =array();
     ';
$eval_blocks  = '';
$eval_foreach = '';
$eval_data    = '
    $data[] = ';
$looplength   = count($array);

for ($i = 0; $i < $looplength; $i++) {
    $eval_foreach .= '
     foreach($array[' . $i . '] as $val' . ($i + 1) . '){
     ';
    if (($i + 1) == $looplength) {
        $eval_data .= ' $val' . ($i + 1) . ';';
    } else {
        $eval_data .= ' $val' . ($i + 1) . ' ." ".';
    }
    $eval_blocks .= '
     }
     ';
}
$eval = $eval . $eval_foreach . $eval_data . $eval_blocks;
eval($eval);
print_r($data);

但如果可能的话，我仍然想找到更好的方法来做到这一点。

更新：

注意：$array是动态的，它可能包含两个或更多子数组

4

5 回答 5

5

我尝试了另一种方法，但最终以类似于 Valentin CLEMENT 的解决方案结束，尽管我的函数更冗长。

尽管如此，独创性在于，此功能为您提供了组合树，这可能（或可能不会）有用，具体取决于您打算做什么。

这是代码：

function getCombinations( $arrayList, $index = 0  )
{
    $subCombinations = $combinations = '';

    if ( $index < count( $arrayList )-1 )
    {
        $subCombinations = getCombinations( $arrayList,  $index+1 );
    }

    foreach( $arrayList[$index] as $item )
    {
        $combinations[$item] = $subCombinations ;
    }
    return $combinations;
}

$combinations = getCombinations( $array );

print_r( $combinations );

使用示例数据：

$array = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l')
);

它将输出：

Array
(
    [a] => Array
        (
            [e] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [f] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [g] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

        )

    [b] => Array
        (
            [e] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [f] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [g] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

        )

    [c] => Array
        (
            [e] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [f] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [g] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

        )

)

然后它需要额外的代码来绘制预期的结果：

function drawCombinations( $combinations, $line = array() )
{
    foreach( $combinations as $value => $children )
    {
        array_push( $line, $value );

        if ( is_array( $children ) ) 
        {
            drawCombinations( $children, $line );
        }
        else
        { 
            echo implode( " ", $line ) ." \n";
        }

        array_pop( $line );
    }

}


drawCombinations( $combinations );

生产 ：

a e h
a e i
a e j
a e k
a e l
a f h
a f i
a f j
a f k
a f l
a g h
a g i
a g j
a g k
a g l
b e h
b e i
b e j
b e k
b e l
b f h
b f i
b f j
b f k
b f l
b g h
b g i
b g j
b g k
b g l
c e h
c e i
c e j
c e k
c e l
c f h
c f i
c f j
c f k
c f l
c g h
c g i
c g j
c g k
c g l

正如我之前所说，如果你不需要这个结果树（你的问题没有提到，我只是在搜索最佳方法时产生了这个），Valentin CLEMENT 的方法可能会更好（如果你不使用太大的数据集，我会在之后解释为什么）。

我重写了一点，我认为它更具可读性和可用性：

function expand( $array, $from = 0, $length = false ) 
{
    if ( $length === false )
    {
        $length = count( $array );
    }

    if ( $length == $from )
    {
        return array('');
    }
    else 
    {
        $result = array();

        foreach( $array[$from] as $x ) 
        {
            foreach( expand( $array, $from+1, $length ) as $tail )
            {
                $result[] = trim("$x $tail");
            }
        }
        return $result;
    }
}


$combinations = expand( $array );

print_r( $combinations );

它返回以下数组：

Array
(
    [0] => a e h
    [1] => a e i
    [2] => a e j
    [3] => a e k
    [4] => a e l
    [5] => a f h
    [6] => a f i
    [7] => a f j
    [8] => a f k
    [9] => a f l
    [10] => a g h
    [11] => a g i
    [12] => a g j
    [13] => a g k
    [14] => a g l
    [15] => b e h
    [16] => b e i
    [17] => b e j
    [18] => b e k
    [19] => b e l
    [20] => b f h
    [21] => b f i
    [22] => b f j
    [23] => b f k
    [24] => b f l
    [25] => b g h
    [26] => b g i
    [27] => b g j
    [28] => b g k
    [29] => b g l
    [30] => c e h
    [31] => c e i
    [32] => c e j
    [33] => c e k
    [34] => c e l
    [35] => c f h
    [36] => c f i
    [37] => c f j
    [38] => c f k
    [39] => c f l
    [40] => c g h
    [41] => c g i
    [42] => c g j
    [43] => c g k
    [44] => c g l
)

然后很容易达到预期的结果：

echo implode( "\n", $combinations )."\n";

将输出：

a e h
a e i
a e j
a e k
a e l
a f h
a f i
a f j
a f k
a f l
a g h
a g i
a g j
a g k
a g l
b e h
b e i
b e j
b e k
b e l
b f h
b f i
b f j
b f k
b f l
b g h
b g i
b g j
b g k
b g l
c e h
c e i
c e j
c e k
c e l
c f h
c f i
c f j
c f k
c f l
c g h
c g i
c g j
c g k
c g l

起初，我认为我的解决方案比 Valentin 的解决方案消耗更多的内存，因为它使用了数组，但是当我测试它时，我意识到它确实使用了更少的内存。

显示针对这两种方法的内存指标给出了这些结果：

drawCombinations(  getCombinations( $array ));

echo memory_get_usage()." ". memory_get_peak_usage()."\n";

// 238736 244896





echo implode( "\n", expand( $array ) )."\n";

echo memory_get_usage()." ". memory_get_peak_usage()."\n";

// 238912 252304

但是当使用更大的输入值时，它变得更加重要，其中：

$array = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l'),
    array('m', 'n', 'o', 'p', 'q', 'r', 's'),
    array('t', 'u', 'v', 'x', 'y', 'z')
);

getCombinations 给出：

drawCombinations(  getCombinations( $array ));

echo memory_get_usage()." ". memory_get_peak_usage()."\n";

// 242376 253008

展开给出：

echo implode( "\n", expand( $array ) )."\n";

echo memory_get_usage()." ". memory_get_peak_usage()."\n";

//242544 704520

如果我们查看每个函数生成的数组，原因很明显，因为第一个解决方案存储的重复值较少（我不确定 PHP 如何处理结束树每个分支的重复数组）。

再一次，取决于您要实现的目标，您是否会关心。

动态地“回显”每一行而不是创建一个大的结果数组，稍微减少了内存峰值问题，但随着数据集的增长，expand() 仍然会消耗更多的内存。

我希望它有所帮助，至少这对我来说很有趣；）

于 2013-08-07T14:09:00.210 回答
4

I first opted for some iteration (counting) based solution directly working on the arrays. As it turned out, this was just a loop with multiple counters. Then I thought, why limit this onto arrays? Why not using a CartesianProductIterator that creates an iteration over the cartesian product of multiple iterators?

It works similar to an AppendIterator and MultipleIterator (see as well: Iterating over Multiple Iterators at Once (Apr 2012; by hakre)) and can be easily used with your array:

$array = [
    ['a', 'b', 'c'],
    ['e', 'f', 'g'],
    ['h', 'i', 'j', 'k', 'l'],
];

$it = new CartesianProductIterator();

foreach($array as $sub)
{
    $it->append(new ArrayIterator($sub));
}

foreach ($it as $tuple)
{
    echo implode(',', $tuple), "\n";
}

The output is as expected:

a,e,h
a,e,i
a,e,j
...
c,g,j
c,g,k
c,g,l

A benefit of such an iterator is that it is more flexible for what it accepts as input.

Also those products can be extremely memory demaning, an iterator is a good tool to reduce memory requirements by solving the problem iteratively.

Another benefit is that an Iterator already keeps track of counting, so the counting problem per each dimension of the product is already solved.

As long as the memory consumption is concerned, instead of an iterator that implements the counting for you, you can do the iteration over all tuples in the product as well with a loop. This variant btw. should actually take care of keys, so should work with different inputs (the example code is reduced for reading):

...

// working loop
$valid = TRUE;
while ($valid)
{
    // create segment
    foreach ($array as $key => $sub)
    {
        echo $sub[$keys[$key][$counters[$key]]];
    }
    echo "\n";

    // count up
    foreach ($order as $key)
    {
        if (++$counters[$key] == $lengths[$key])
        {
            $counters[$key] = 0;
            continue;
        }
        continue 2;
    }
    $valid = FALSE;
};

As this example shows, each iteration in the loop outputs one tuple of the product, so memory requirements are low, too. If you replace the echo with a yield statement this is a good boilerplate to create a generator from.

As the CartesianProdcutIterator is an object so it can do a little more than a loop or generator, therefore it has some more features: You can specify the iteration or counting or sort mode: Move on the last iterator first (default), or the first first:

$it = new CartesianProductIterator(CartesianProductIterator::ORDER_FIRST_FIRST);

This will do the following iteration:

a,e,h
b,e,h
c,e,h
...
a,g,l
b,g,l
c,g,l

But not only that, it can be even controlled more by specifying a $countOrder parameter when appending. It specifies the actual sort-keys to be ordered on by the order-mode:

$array = [
    0 => ['a', 'b', 'c'],
    2 => ['e', 'f', 'g'],
    1 => ['h', 'i', 'j', 'k', 'l'],
];

$it = new CartesianProductIterator();

foreach($array as $countOrder => $sub)
{
    $it->append(new ArrayIterator($sub), $countOrder);
}

foreach ($it as $tuple)
{
    echo implode(',', $tuple), "\n";
}

This (as the default mode is last-first) specifies to first iterate in the middle (e-g), then at the end (h-l) and then on the first one (a-c):

a,e,h
a,f,h
a,g,h
a,e,i
...
c,g,k
c,e,l
c,f,l
c,g,l

Hope this is helpful and qualifies as "a better way".

于 2013-08-11T08:57:42.893 回答
1

你们提出的出色算法给我留下了深刻的印象。但是我认为 PHP 中的正确方法是使用迭代器：http: //php.net/manual/fr/class.iterator.php

我实施了一个示例，说明您可以为您的问题做些什么。

类 CombinationIterator 实现 Iterator {
    私人$位置= 0；
    私人 $array = array();

    公共函数 __construct($array) {
        $this->array = $array;
        $this->position = array_fill(0,sizeof($this->array),0);
    }

    函数倒带（）{
        $this->position = array_fill(0,sizeof($this->array),0);
    }

    功能电流（）{
        $word = 数组（）；
        foreach ($this->position as $i=>$pos) {
            $word[]=$this->array[$i][$pos];
        }
        返回内爆（“”，$字）；
    }

    功能键（）{
        返回 $this-> 位置；
    }
    功能下一个（）{
        foreach (array_reverse($this->position,true) as $i=>$pos) {
            # 如果此数组中的位置已到末尾，则将其设置为 0 并增加下一个
            if ($pos == sizeof($this->array[$i])-1) {
                $this->位置[$i] = 0;
                if (array_key_exists($i-1,$this->position)) {
                    继续;
                } 别的 {
                    $this->rewind();
                }
                休息;
            } 别的 {
                $this->位置[$i]++;
                休息;
            }

        }
    }
    函数有效（）{
        $有效=假；
        foreach ($this->position as $i=>$pos) {
            if ($pos < sizeof($this->array[$i])-1) { return true; }
        }
        返回$有效；
    }

}

以下是您如何使用它来显示您的文字：

$数组 = 数组（
    数组（'a'，'b'，'c'），
    数组（'e'，'f'，'g'），
    数组（'h'，'i'，'j'，'k'，'l'），
    数组（'m'，'n'，'o'，'p'，'q'，'r'，'s'），
    数组（'t'，'u'，'v'，'x'，'y'，'z'）
);


$c = new CombinationIterator($array);
而 ($c->valid()) {
    echo $c->current()."\n";
    $c->下一个();
}

我没有编写 previous() 方法，但您可以轻松地从 next() 方法创建它。

此外，这里的内存使用率非常低，因为您只能获取存储的位置。

我希望它能对你的项目有所帮助。

再见

于 2013-08-09T13:10:03.253 回答
1

这应该有效：

function expand($arr){
    function recexpand($arr, $from, $len) {
        if ($from == $len) {
            yield "\n";
        } else {
            foreach($arr[$from] as $x) {
                foreach(expand($arr, $from+1, $len) as $tail) {
                    yield "$x $tail";
                }
            }
        }
    }
    return recexpand($arr, 0, count($arr);
}
$array = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l')
);
foreach(expand($array) as $row) {
    echo $row;
}

回声：

a e h
a e i
a e j
a e k
a e l
a f h
a f i
a f j
a f k
a f l
a g h
a g i
a g j
a g k
a g l
b e h
b e i
b e j
b e k
b e l
b f h
b f i
b f j
b f k
b f l
b g h
b g i
b g j
b g k
b g l
c e h
c e i
c e j
c e k
c e l
c f h
c f i
c f j
c f k
c f l
c g h
c g i
c g j
c g k
c g l

我不是一个 PHP 人，所以可能有一种更惯用的方式来编写它，但它适用于任何长度的数组。

对于 PHP<5（或任何没有 'yield' 声明的版本）

function expand($arr) {
    function recexpand($arr, $from, $len) {
        if ($from == $len) {
            return array("\n");
        } else {
            $result = array();
            foreach($arr[$from] as $x) {
                foreach(expand($arr, $from+1, $len) as $tail) {
                    $result[] = "$x " . $tail;
                }
            }
            return $result;
        }
    }
    return recexpand($arr, 0, count($arr));
}
$arr = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l')
);
foreach(expand($arr) as $row) {
    echo "$row";
}
于 2013-08-06T12:08:21.453 回答
1

我的非递归方式：

<?php
$array = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l')
);

$upperBounds = array();
foreach ($array as $arr) {
    $upperBounds[] = count($arr);
}

$counterArray = array_pad(array(), count($array), 0);

do {
    foreach ($counterArray as $key => $c) {
        echo $array[$key][$c];
    }
    echo PHP_EOL;
} while (incrementCounter($counterArray, $upperBounds));

function incrementCounter(&$counterArray, $upperBounds)
{
    if (count($counterArray) == 0 || count($counterArray) != count($upperBounds)) {
        return false;
    }
    $counterArray[0]++;
    foreach ($counterArray as $key => $value) {
        if ($counterArray[$key] >= $upperBounds[$key]) {
            $counterArray[$key] = 0;
            if (isset($counterArray[$key+1])) {
                $counterArray[$key+1]++;
            }
            else {
                $counterArray[$key+1] = 1;
                return false;
            }
        }
        else {
            break;
        }
    }
    return true;
}
于 2013-08-11T07:45:47.697 回答