1

私のアルファベットには X 文字が含まれており、私の言語は Y 文字の単語 (もちろん Y < X) のみをサポートしているとします。ランダムな順序で可能なすべての単語を生成する必要があります。

例: Alphabet=a,b,c,d,e,f,g Y=3

したがって、単語は次のようになります: aaa aab aac aba .. bbb ccc .. (上記はランダムな順序で生成される必要があります)

それを行う簡単な方法は、単語を生成してからリストをランダム化することです。私はそれをしたくありません。ランダムな順序で単語を生成したい。

rondom(n)=letter[x].random(n-1) は機能しません。これは、letter[x].. で始まる単語のリストが作成され、リストがそれほどランダムでなくなるためです。

任意のコード/疑似コードを歓迎します。

4

3 に答える 3

1

他の回答が示唆しているように、2つの主なアプローチがあります：1）すでに生成したものを追跡する（このカテゴリで提案されたソリューションはおそらく決して終了しないという問題があります）、または2）まだ生成されていない順列を追跡します（これは、順列は事前に生成する必要がありますが、これは要件で特に許可されていません）。終了が保証され、事前生成を必要としないが、ランダム化要件（現時点ではあいまいです）を満たさない可能性がある別のソリューションを次に示します。

一般的な概要：ツリーを生成して、生成されたものまたは残っているものを追跡します。ツリー内のランダムなリンクをトラバースし、その順列の生成後にリーフでツリーを剪定して、それが再度生成されないようにすることで、新しい順列を「選択」します。

これを図解するためのホワイトボードがなくても、この説明が私が何を意味するかを説明するのに十分であることを願っています。アルファベットのすべての文字について他のノードへのリンクを持つ「ノード」を作成します。これは、ノードへのアルファベット文字の一般的なマップを使用して実装できます。または、アルファベットが固定されている場合は、特定の参照を作成できます。ノードは、順列を生成するために次に「生成」できるアルファベットの使用可能な文字を表します。ルートノードにアクセスし、そのノードで使用可能な文字からランダムな文字を選択し、その参照を次のノードにトラバースすることで、順列の生成を開始します。トラバーサルごとに、順列の文字が生成されます。葉に到達したとき（つまり、順列が完全に構築されたとき）、あなたは dツリーをバックトラックして、親ノードに使用可能な順列が残っているかどうかを確認します。そうでない場合は、親ノードをプルーニングできます。

実装の詳細として、ノードは、その時点で生成できない文字のセット、またはその時点でまだ生成できる文字のセットを格納できます。ストレージ要件を減らすために、ノードがアルファベットの半分以上を許可するときに、これまでに生成された文字を保存し、残りの文字を使用するように切り替えるように、ノードが実行していることを示すフラグを使用して保存することもできます。利用できるアルファベットの半分未満です。

このようなツリー構造を使用すると、ツリー全体を事前に構築する必要がないため（順列が生成されるときに構築できます）、すべての組み合わせを事前に生成しなくても生成できるものが制限されます。ノードのパージ（つまり、生成されていない順列の許可された組み合わせである場合にのみ、ノードへのリンクをトラバースしている）。

ただし、この手法のランダム化は少し奇妙だと思います。実際には考えていませんが、各組み合わせがいつでも同じように生成される可能性は低いと思います。また、ツリー全体が必ずしも前もって生成されるとは限らない場合でも、関連するオーバーヘッドは十分であるため、すべての順列を事前に生成する方がよい場合があることにも注意してください。

于 2009-06-22T16:09:05.710 に答える
0

だから私はあなたが望むのは、できるだけ少ないメモリを使ってセットの順列を生成することだと思います.

まず、メモリがないとできません。最初の文字列には、どの文字列も同じ確率で生成できる関数が必要です。関数が nextString() と呼ばれているとします。状態を何も変更せずに nextString() を再度呼び出すと、もちろん、文字列を生成できるようになります。

そのため、何かを保存する必要があります。問題は、何を保管する必要があり、どのくらいのスペースが必要かということです。

文字列は、0 から X^Y までの数字として表示されます。(aaa=0, aab=1,aac=2...aba=X...) したがって、1 つの文字列をできるだけ効率的に格納するには、lg(X^Y) ビットが必要になります。X = 16、Y = 2 としましょう。次に、文字列を一意に指定するために 1 バイトのストレージが必要になります。

もちろん、最も素朴なアルゴリズムは、生成された各文字列をマークすることです。これには X^Y ビットが必要で、私の例では 256 ビット (32 バイト) です。これはあなたがやりたくないと言ったことです。この質問で説明されているように、シャッフル アルゴリズムを使用できます:順序付きリストからランダムな順序付きリストを作成する(シャッフル アルゴリズムを使用して文字列を生成するときに文字列を保存する必要はありませんが、それでもマークを付ける必要があります)。

さて、問題は、それよりもうまくやれるかどうかです。合計でどれくらい保存する必要がありますか?

最初の呼び出しでは、ストレージは必要ありません。2 回目の呼び出しでは、どちらが以前に生成されたかを知る必要があります。最後の呼び出しでは、どれが最後に残っているかを知る必要があるだけです。したがって、最悪のケースは、途中である場合です。途中で128本の弦が出来上がり、残り128本。生産するために残っているものを知る必要があります。プロセスが完全にランダムであると仮定すると、任意の分割が可能です。(256 が 128 を選択) の可能性があります。これらのいずれかを潜在的に格納できるようにするには、lg(256 choose 128) ビットが必要です。これは、Google 計算機によると 251.67. したがって、あなたが本当に賢いなら、単純なアルゴリズムよりも 4 ビット少ないビットに情報を絞り込むことができます。おそらくそれだけの価値はありません。

非常に少ないストレージでランダムに見えるようにしたい場合は、次の質問を参照してください：（疑似）ランダムな順序で一連の数字を吐き出すアルゴリズムを探しています

于 2009-06-22T15:21:14.167 に答える
0

あなたが持っているアルファベットに基づいて文字のランダムな配列を生成することで、かなり簡単なことを行うことができると思います（C＃で）：

        char[] alphabet = {'a', 'b', 'c', 'd'};
        int wordLength = 3;

        Random rand = new Random();

        for (int i = 0; i < 5; i++)
        {
            char[] word = new char[wordLength];
            for (int j = 0; j < wordLength; j++)
            {
                word[j] = alphabet[rand.Next(alphabet.Length)];
            }
            Console.WriteLine(new string(word));
        }

明らかに、これにより重複が生成される可能性がありますが、必要に応じて結果をハッシュマップまたは何かに保存して重複を確認できます。

于 2008-12-14T19:18:02.113 に答える