用php合并递归函数中的数组？

Question

一周后，搜索并将许多算法从其他语言转换成php，生成一个包含“组合k from n”的数组。我被卡住了。请帮帮我。

这是我的代码(使用php)：

function comb($item,$arr,$out, $start, $n, $k, $maxk) {
if ($k > $maxk) {
       foreach($arr as $ar){
           echo "$ar";
           echo "<br/>";
       }
   return;
}

for ($i=$start; $i<=$n; $i++) {
     $arr[$k] = $item[$i-1];
         comb($isi, $arr, $out, $i+1, $n, $k+1, $maxk);
}
}

$team = array("A","B","C","D");
$ar = array();
$o = array();
comb($team,$ar,$o,1,4,1,2);

上面的递归算法真的把我搞糊涂了。上面的代码成功地形成了组合，但我不能将它们合并到一个数组中，因为它的递归特性。我只想做一个数组，包含4项中2项的组合结果。像这样(见下文)

Array (
   [0] => Array (
                  [1] => A
                  [2] => B
          )

   [1] => Array (
                  [1] => A
                  [2] => C
          )

   [2] => Array (
                  [1] => A
                  [2] => D
          )

   [3] => Array (
                  [1] => B
                  [2] => C
          )

   [4] => Array (
                  [1] => B
                  [2] => D
          )

   [5] => Array (
                  [1] => C
                  [2] => D
          )
)

我知道我离答案还很远。但是，请指引我，以达到这个答案。也许你知道另一种技术，这无关紧要。如果你的代码行得通，我会用它。不管你用过什么技术。任何想法都将不胜感激，谢谢..！

Answer 1

一个(我认为)更简单的递归实现是：

<?php

/* Given the array $A, returns the array of $k-subsets
   of $A in lexicographical order. */
function k_lex_subset($A,$k) {
  if (($k <= 0) or (count($A) < $k)) { return array(); }
  else if ($k <= 1) { return array_chunk($A,1); }
  else {
    $v = array_shift($A);
    $AwA = k_lex_subset($A,$k-1);
    foreach($AwA as &$vp) {
      array_unshift($vp,$v);
    }
    $AwoA = k_lex_subset($A,$k);
    $resultArrs = array_merge($AwA, $AwoA);
    return($resultArrs);
  }
}

$team = array("A","B","C","D");
print_r(k_lex_subset($team,2));


?>

它会返回

Array
(
    [0] => Array
        (
            [0] => A
            [1] => B
        )

    [1] => Array
        (
            [0] => A
            [1] => C
        )

    [2] => Array
        (
            [0] => A
            [1] => D
        )

    [3] => Array
        (
            [0] => B
            [1] => C
        )

    [4] => Array
        (
            [0] => B
            [1] => D
        )

    [5] => Array
        (
            [0] => C
            [1] => D
        )

)

适用于任何大小的数组和任何$k。

您要查找的术语是(字典学)k子集枚举，其中$k在此特定情况下为2。

说明

这个想法非常简单。假设我们(例如)有一个集合{A,B,C,D}。我们想要从所有包含A的集合开始，因此我们考虑大小为1的子集-小于来自{B,C,D}的子集，并将A附加到它们上，从而产生

{{A,B}, {A,C}, {A,D}}

然后我们考虑大小为2而没有A的所有子集

{{B,C}, {B,D}, {C,D}}

然后我们把这两个合并。希望很容易看出，一般来说，这是如何产生一个很好的递归策略来构造一个集合的k-子集(而不仅仅是k=2)。

参考

关于这类事情的一个很棒的参考资料是Vol 4 Fasicle 3 of Knuth's The Art of Computing Programming。

Answer 2

这应该可以达到您上面描述的数组：

<?php
$array = array("A","B","C","D");

function transformArray( $array ) {

    $returnArray = array();

    for( $i=0; $i < count($array); $i++ ) {

        for( $j=$i+1; $j < count($array); $j++ ) {

            $returnArray[] = array( $array[$i], $array[$j] );

        }

    }

    return $returnArray;

}

print_r(transformArray($array));
?>

Answer 3

function comb($a, $len){
    if ($len > count($a))return array();
    $out = array();
    if ($len==1) {
        foreach ($a as $v) $out[] = array($v);
        return $out;
    }
    $len--;
    while (count($a) > $len) {
        $b = array_shift($a);
        $c = comb($a, $len);
        foreach ($c as $v){
            array_unshift($v, $b);
            $out[] = $v;
        }
    }
    return $out;
}

$test = array('a','b','c','d');
$a = comb($test,2);
print_r($a);

会给你带来：

Array(
[0] => Array
    (
        [0] => a
        [1] => b
    )

[1] => Array
    (
        [0] => a
        [1] => c
    )

[2] => Array
    (
        [0] => a
        [1] => d
    )

[3] => Array
    (
        [0] => b
        [1] => c
    )

[4] => Array
    (
        [0] => b
        [1] => d
    )

[5] => Array
    (
        [0] => c
        [1] => d
    )

)