16

私は、数字や単語を取り、それらのすべての可能なバリエーションを一緒に見つけ、一緒に探す値の数を定義できるアルゴリズムを探しています。

たとえば、文字列または配列は次のとおりです。 

cat  
dog  
fish

その場合、値2の結果は次のようになります。 

cat dog  
cat fish  
dog cat  
dog fish  
fish cat  
fish dog

したがって、3つのアイテムのセットからの結果は、2つの結果が一致する6つの可能なバリエーションであり
、3つの結果が一致すると次のようになります。 

cat dog fish  
cat fish dog  
dog cat fish  
dog fish cat  
fish cat dog  
fish dog cat

...おそらくもっと多くのオプションさえ

Stackoverflowでこれを行うこの例へのリンクを見つけましたが、これはjavascriptにあります。誰かが、PHPでこれを行う方法を知っているかどうか疑問に思っています。おそらく、すでに何かが構築されているのでしょうか。

http://www.merriampark.com/comb.htm（リンク切れ）

4

2 に答える 2

24

http://pear.php.net/package/Math_Combinatoricsをご覧ください

<?php
require_once 'Math/Combinatorics.php';
$words = array('cat', 'dog', 'fish');
$combinatorics = new Math_Combinatorics;
foreach($combinatorics->permutations($words, 2) as $p) {
  echo join(' ', $p), "\n"; 
}

プリント

cat dog
dog cat
cat fish
fish cat
dog fish
fish dog
于 2009-08-10T17:25:05.087 に答える
15

このようなものがどのように機能するかを探しているなら、これは私がバイナリを使用してphpライブラリなしでそれを達成した方法です。

function search_get_combos($query){
$list = explode(" ", $query);
$bits = count($list); //bits of binary number equal to number of words in query;
//Convert decimal number to binary with set number of bits, and split into array
$dec = 1;
$binary = str_split(str_pad(decbin($dec), $bits, '0', STR_PAD_LEFT));
while($dec < pow(2, $bits)) {
    //Each 'word' is linked to a bit of the binary number.
    //Whenever the bit is '1' its added to the current term.
    $curterm = "";
    $i = 0;
    while($i < ($bits)){
        if($binary[$i] == 1) {
            $curterm .= $list[$i]." ";
        }
        $i++;
    }
    $terms[] = $curterm;
    //Count up by 1
    $dec++;
    $binary = str_split(str_pad(decbin($dec), $bits, '0', STR_PAD_LEFT));
}
return $terms;
}

ただし、これは一意の組み合わせのみを返すことに注意してください。ただし、組み合わせの可能なすべての順序を取得するように簡単に拡張できるため、この例では次のように出力されます。

Array
(
    [0] => fish 
    [1] => dog 
    [2] => dog fish 
    [3] => cat 
    [4] => cat fish 
    [5] => cat dog 
    [6] => cat dog fish 
)

編集（より明確にする）

基礎理論

したがって、最初に、おそらくご存知のように、2進数は1と0の文字列です。数の長さは、それが持つ「ビット」の数です。数字011001は6ビットです（興味がある場合は数字25）。次に、数値の各ビットが用語の1つに対応する場合、カウントアップするたびに、ビットが1の場合、用語は出力に含まれますが、0の場合は無視されます。これが、何が起こっているかについての基本的な理論です。

コードを掘り下げる

PHPには2進数で数える方法はありませんが、小数を2進数に変換することはできます。したがって、この関数は実際には10進数でカウントアップし、それを2進数に変換します。ただし、ビット数が重要であるため、各項には独自のビットが必要であるため、先行ゼロを追加する必要があります。これにより、このビットの機能は次のようになります。str_pad(decbin($dec), $bits, '0', STR_PAD_LEFT)

現在、この関数はwhileループを使用していますが、ループする必要がある回数は用語の数によって異なるため、少し計算を行う必要があります。バイナリを使用したことがある場合は、作成できる最大数が2 ^ n（nはビット数）であることがわかります。

関数の紛らわしい部分をすべてカバーする必要があったと思います。何か見落としがあった場合はお知らせください。

何が起こっているかを見る

次のコードを使用して、使用されているロジックを出力します。このように見ると、もう少し意味があるかもしれません。

function search_get_combos_demo($query){
    $list = explode(" ", $query);
    $bits = count($list);
    $dec = 1;
    while($dec < pow(2, $bits)) {
        $binary = str_split(str_pad(decbin($dec), $bits, '0', STR_PAD_LEFT));
        $curterm = "";
        $i = 0;
        while($i < ($bits)){
            if($binary[$i] == 1) {
                $curterm[] = $list[$i]." ";
            }
            $i++;
        }
        //-----DISPLAY PROCESS-----//
        echo "Iteration: $dec <table cellpadding=\"5\" border=\"1\"><tr>";
        foreach($binary as $b){
            echo "<td>$b</td>";
        }
        echo "</tr><tr>";
        foreach($list as $l){
            echo "<td>$l</td>";
        }
        echo "</tr></table>Output: ";
        foreach($curterm as $c){
            echo $c." ";
        }
        echo "<br><br>";
        //-----END DISPLAY PROCESS-----//
        $terms[] = $curterm;
        $dec++;
    }
    return $terms;
}
于 2013-06-12T19:53:42.620 に答える