2

经过一周搜索并将许多算法从其他语言转换为 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
          )
)

我知道我离答案还很远。但请指导我，以达到那个答案。也许你知道其他技术，没关系。如果您的代码有效，我将使用它。不管你使用了什么技术。任何想法将不胜感激，谢谢..！

4

6 回答 6

3

一个（我认为）更简单的递归实现是：

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

解释

这个想法很简单。假设我们有（例如）一个 set {A,B,C,D}。我们想从所有包含 A 的集合开始，因此我们考虑大小为 1 的子集来自{B,C,D}并将 A 附加到它们产生

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

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

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

然后我们将两者合并。希望很容易看出，一般来说，这会产生一个很好的递归策略来构造一个集合的 k 个子集（而不仅仅是 k=2）。

参考

Knuth 的 The Art of Computing Programming 的第 4 卷 Fasicle 3是关于这类事情的绝佳参考。

于 2012-03-18T15:58:53.563 回答
1

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

<?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));
?>
于 2012-03-18T15:40:05.510 回答
1 
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
    )

)

于 2012-03-18T15:50:48.000 回答
1

不完全确定 start、n 和 k 的必要性，但这应该可以得到预期的输出。如果您提供有关为什么需要这些计数器的更多详细信息，我们可以为您提供更全面的答案。

function comb($itemArray, $start, $n, $k, $maxk) {

    //if ($k > $maxk) return;

   $outputArray = array();

    foreach($itemArray AS $index => $firstChar) {

        for($i = $index+1; $i<count($itemArray); $i++) {

            $secondChar = $itemArray[$i];

            $outputArray[] = array($firstChar, $secondChar);

        }

    }

    return $outputArray;

}

$teamArray = array("A","B","C","D");

$resultArray = comb($teamArray,1,4,1,2);

ppr($resultArray);

function ppr($variable) {

    echo '<pre>';

    print_r($variable);

    echo '</pre>';

}
于 2012-03-18T15:52:04.217 回答
0

你为什么这样做

echo "ar"

代替

echo $ar

您还在寻找排列或组合吗？这是一个对两者都有非常好的算法的站点。实现是在java中，但它非常清楚。所以转换为 php 并不困难： http: //geekviewpoint.com/Numbers_functions_in_java/

于 2012-03-18T15:51:33.600 回答
0

如果你想要一个纯粹的递归方式使用这个：

function comb($item, $n) {
    return comb_rec($item, array(), $n);
}
function comb_rec($items, $c, $n) {
    if (count($c) == $n) {
        return array($c);
    }else{
        if (count($items) == 0) {
            return $items;
        }else{
            $list = $items;
            $head = array_shift($list);
            $tail = $list;
            $current = $c;
            array_push($current,$head);
            return array_merge(comb_rec($tail, $current, $n),comb_rec($tail, $c, $n));
        }
    }

}

$team = array("A","B","C","D");
$all = comb($team,2);
print_r($all);
于 2012-03-18T17:09:45.983 回答