php - 使用php在递归函数中合并数组？

Question

经过一周的搜索并将许多算法从其他语言转换为 php 来制作一个包含“n 的 k 组合”的数组。我被困住了。请帮我。

这是我的代码(使用 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 的集合开始，因此我们考虑来自 {B,C,D} 的大小小于 1 的子集，并将 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 .