2

1週間後、多くのアルゴリズムを他の言語から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);

上記の再帰アルゴリズムは本当に私を混乱させます。上記のコードは組み合わせを形成することに成功しましたが、再帰的な特性のため、それらを 1 つの配列にマージすることはできません。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}}

そして、2つをマージするだけです。一般に、これにより、セットの k-サブセットを構築するための優れた再帰的戦略がどのように得られるかが簡単にわかることを願っています (単なる k=2 ではなく)。

参照

この種の素晴らしいリファレンスは、Knuth の The Art of Computing Programming の Vol 4 Fasicle 3 です。

于 2012-03-18T15:58:53.563 に答える
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 に答える
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 に答える
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 に答える