1

私には興味深い問題があり、私の人生では、良い解決策を見つけることができません。0+「トークン」を含むフレーズが与えられます。例えば：

なんと%A1%牛。%A2% には奇妙な形の %A3% がありました。

上記の 、%A1%、%A2%および%A3%はすべて「トークン」です。各トークンには、その代わりに使用できる可能性のある単語の独自のリストがあります。

public class Token {
    // Ex: %A1%
    private String code;

    // Ex: "brown", "red", "silly"
    private List<String> candidates;
}

任意のフレーズ (上記の例だけでなく) を取得し、トークンの存在をスキャンするコードを作成する必要があります。トークンが見つかった場合は、各トークンの候補リストのすべての組み合わせを使用して、フレーズのすべての順列を生成する必要があります。たとえば、上記の 3 つのトークンに対して次の候補が存在した場合:

%A1%
====
brown
red
silly

%A2%
====
arsonist
banker

%A3%
====
feet
hands

次に、次の文順列が生成されます。

How now brown cow. The arsonist had oddly-shaped feet.
How now brown cow. The arsonist had oddly-shaped hands.
How now brown cow. The banker had oddly-shaped feet.
How now brown cow. The banker had oddly-shaped hands.
How now red cow. The arsonist had oddly-shaped feet.
How now red cow. The arsonist had oddly-shaped hands.
How now red cow. The banker had oddly-shaped feet.
How now red cow. The banker had oddly-shaped hands.
How now silly cow. The arsonist had oddly-shaped feet.
How now silly cow. The arsonist had oddly-shaped hands.
How now silly cow. The banker had oddly-shaped feet.
How now silly cow. The banker had oddly-shaped hands.

%A1%には 3 つの可能な値があり、%A2%とにはそれぞれ 2 つの可能な値があるため%A3%、合計で 3 x 2 x 2 = 12 の順列があります。

フレーズ内のトークンの数が常に一定である場合、問題は (少なくとも私にとっては) はるかに簡単になります。しかし、問題は次のとおりです。

  1. フレーズに含まれるトークンの数はわかりません (0 個のトークンが含まれる場合もあります)。と
  2. どのトークン (したがって、どの候補リスト) が各フレーズに表示されるかはわかりません。そのため、フレーズをスキャンしてトークンのリストを取得し、それらを「順列ジェネレーター」に動的に挿入できるようにする必要があります。必要です。

どういうわけか、私はこれについて頭を悩ませることができません。これをどのようにコーディングできるかについてのアイデアはありますか? 前もって感謝します！

4

3 に答える 3

1

再帰関数を使用して、すべての順列を取得できます。この疑似コードのようなもの:

void applyAllTokens(string s, stack<string> token_names) {
     if (token_names.isEmpty()) { 
         print(s);
         return;
     }
     top_name = token_names.pop();
     foreach (string token_value in map[top_name]) {
         string t = replaceToken(s,top_name,token_value);
         applyAllTokens(t,token_names.copy());
     }
}
于 2013-10-23T21:25:51.987 に答える
0

フレーズをスキャンしてList、L トークンの TokenList を取得します。リストの各要素は、Listそのトークンの候補の TokenList[i] にマップされ、i は [0,L) に含まれます。

TokenList[0] = [ Cow, Fox, Dog ]
TokenList[1] = [ Rapist, Arsonist, Murderer, Rapist ]
TokenList[2] = [ Feet, Shoulders, Knees, Toes ]
...

ここで、候補のインスタンスのリスト (例: [ Cow, Arsonist, Feet ]) とその数のトークンを持つフレーズを取得し、トークンを置き換える関数が必要です。

あなたの問題は、リストのリストからすべてのインスタンスリストを生成する方法になります。別の回答で説明されているように、これは再帰的に行うことができます。

プラットフォームの最大整数値より小さい数値については、これを繰り返し行うことができます。最初に反復回数を計算します。これは、すべての L 個のリストのサイズ N の積になります。

今、

for (i = 0; i < N; i++) {
    R = i
    Tokens = [ ]
    for (j = 0; j < L; j++) {
        Tokens[j] = TokenList[ R % TokenList[j].length ]
        R /= TokenList[j].length
    }
    generateSentence(template, Tokens)
}

すべての組み合わせを順番に生成します。

于 2013-10-23T21:47:07.810 に答える
-1

その日の帰宅前に大まかな概要を...

入力フレーズにトークンの使用以外は含まれないと仮定すると、シンボル%で使用できます。結果の配列では、トークンと非トークンが交互に表示されます。このようにして、存在するトークンの数を簡単に数えることができます。split()%

次に、どれがトークンであるかを確認する方法が必要です。それらがすべて form の場合A#、これは非常に簡単なはずです。最初のもの（0）を確認してください。それがトークンの場合、すべての偶数要素もトークンです。そうでない場合、奇妙なものはトークンです。

各トークンのインデックスを個別の構造体に格納します。おそらく、Mapトークン名をキーとして、配列インデックスを値として格納します。

順列のリストを取得したら、フレーズを再び結合して、それぞれの新しい String 配列にすることができます。A1トークン以外の部分をコピーしてから、マップされたインデックスをチェックして、たとえばトークンがどこにあるかを確認します。

于 2013-10-23T20:21:51.710 に答える