4

使用頻度の高い順にソートされた一般的な単語のリストが与えられた場合、「最も一般的な」シーケンスの順序で、任意の長さ (任意の数の単語) の単語の組み合わせを形成することが可能です。たとえば、最も一般的な単語が「a、b、c」である場合、長さ 2 の組み合わせについては、次のように生成されます。

aa
ab
ba
bb
ac
bc
ca
cb
cc

長さ 3 の正しいリストは次のとおりです。

aaa
aab
aba
abb
baa
bab
bba
bbb
aac
abc
bac
bbc
aca
acb
bca
bcb
acc
bcc
caa
cab
cba
cbb
cac
cbc
cca
ccb
ccc

これは、任意の数の要素に対して 2 つまたは 3 つの単語 (長さを設定) の組み合わせに対して実装するのは簡単ですが、これは任意の長さに対して実行できますか? これを PHP で実装したいのですが、疑似コードやアルゴリズムの要約さえあれば大歓迎です!

4

4 に答える 4

1

これは、必要な再帰関数です。アイデアは、長さと文字が与えられると、その文字を含まない 1 文字短いすべてのシーケンスを最初に生成することです。最後に新しい文字を追加すると、その文字を含むシーケンスの最初の部分が得られます。次に、新しい文字を左に移動します。右側の新しい文字を含む文字の各シーケンスを循環します。

したがって、gen(5, d) があれば、次のように始まります。

(aaaa)d
(aaab)d
...
(cccc)d

それがACの組み合わせで終わったら、それはするでしょう

(aaa)d(a)
...
(aaa)d(d)
(aab)d(d)
... 
(ccc)d(d)

次に、d を 4 番目の文字として使用すると、3 番目の文字に移動します。

(aa)d(aa)

などなど

<?php 
/** 
 * Word Combinations (version c) 6/22/2009 1:20:14 PM 
 * 
 * Based on pseudocode in answer provided by Erika: 
 *   http://stackoverflow.com/questions/1024471/generating-ordered-weighted-combinations-of-arbitrary-length-in-php/1028356#1028356 
 *   (direct link to Erika's answer) 
 * 
 * To see the results of this script, run it: 
 *   http://stage.dustinfineout.com/stackoverflow/20090622/word_combinations_c.php 
**/ 

init_generator(); 

function init_generator() { 
    global $words; 
    $words = array('a','b','c'); 
    generate_all(5);


} 

function generate_all($len){
    global $words;
    for($i = 0; $i < count($words); $i++){
        $res = generate($len, $i); 

        echo join("<br />", $res);  
        echo("<br/>");
    }   
}

function generate($len, $max_index = -1){ 
    global $words; 

    // WHEN max_index IS NEGATIVE, STARTING POSITION 
    if ($max_index < 0) { 
        $max_index = count($words) - 1; 
    } 

    $list = array(); 


    if ($len <= 0) { 
        $list[] = "";
        return $list; 
    } 

    if ($len == 1) { 

        if ($max_index >= 1) { 
            $add = generate(1, ($max_index - 1));
            foreach ($add as $addit) { 
                $list[] = $addit; 
            } 


        } 
        $list[] = $words[$max_index]; 
        return $list; 
    } 

    if($max_index == 0) { 
        $list[] = str_repeat($words[$max_index], $len); 
        return $list; 
    } 

    for ($i = 1; $i <= $len; $i++){ 
        $prefixes = generate(($len - $i), ($max_index - 1)); 
        $postfixes = generate(($i - 1), $max_index); 
        foreach ($prefixes as $pre){ 
            //print "prefix = $pre<br/>";
            foreach ($postfixes as $post){ 
                //print "postfix = $post<br/>";
                $list[] = ($pre . $words[$max_index] . $post); 
            } 
        } 
    } 
    return $list; 
} 

?>
于 2009-06-22T17:05:49.040 に答える
0

私はphp順列をグーグルで検索し、得ました：http://www.php.happycodings.com/Algorithms/code21.html

コードが良いかどうかは調べていません。しかし、それはあなたが望むことをするようです。

于 2009-06-21T18:42:18.133 に答える
0

あなたが計算しようとしているものの用語が何であるかはわかりませんが、それは組み合わせでも順列でもなく、ある種の繰り返しのある順列です。

以下に、私が横たわっている最も近いもの、LPC の文字列順列ジェネレーターからわずかに適応したコードをいくつか同封しました。a、b、cの場合、生成します

abc
bac
bca
acb
cab
cba

おそらく、必要な繰り返し動作を有効にするために微調整できます。

varargs mixed array permutations(mixed array list, int num) {
    mixed array out = ({});
    foreach(mixed item : permutations(list[1..], num - 1))
        for(int i = 0, int j = sizeof(item); i <= j; i++)
            out += ({ implode(item[0 .. i - 1] + ({ list[0] }) + item[i..], "") });
    if(num < sizeof(list))
        out += permutations(list[1..], num);
    return out;
}

FWIW、問題を別の方法で述べると、N 要素の入力の場合、入力要素をノードとして持つ完全接続自己接続グラフで、長さ N のすべてのパスのセットが必要です。

于 2009-06-21T18:48:00.700 に答える
0

固定長が簡単だと言うとき、 mはシーケンスの長さ (例では 2 と 3) であるm 個のネストされたループを使用していると思います。

次のように再帰を使用できます。

単語には 0、1、.. n の番号が付けられています。長さmのすべてのシーケンスを生成する必要があります。

generate all sequences of length m:
{
    start with 0, and generate all sequences of length m-1
    start with 1, and generate all sequences of length m-1
    ...
    start with n, and generate all sequences of length m-1 
}

generate all sequences of length 0
{
    // nothing to do
}

これを実装する方法は？各呼び出しで、もう 1 つの要素を配列の最後にプッシュできます。再帰の最後に到達すると、配列の内容を出力します。

// m is remaining length of sequence, elements is array with numbers so far
generate(m, elements)
{
    if (m == 0)
    {
        for j = 0 to elements.length print(words[j]);
    }
    else
    {
        for i = 0 to n - 1
        {
            generate(m-1, elements.push(i));
        }   
    }
}

最後に、次のように呼び出します: generate(6, array())

于 2009-06-21T19:14:45.537 に答える