c - 単語をスクランブルするアルゴリズムはありますか?

Question

単語スクランブラーを作成しようとしていますが、使用すべきアルゴリズムがあるかどうか、またはゼロから構築する必要があるかどうか疑問に思っています。どんなポインタも役に立ちます！

Answer 1

一連の要素 (または、あなたの場合は単語内の文字) のランダムな順列を見つけるための標準的なアルゴリズムは、Fisher-Yates shuffleです。これは、要素のシーケンスの真にランダムな順列を線形時間で生成します。このアルゴリズムは十分に確立されており、多くの標準ライブラリがその実装を提供しているため (たとえば、C++std::random_shuffleアルゴリズムは通常、このアルゴリズムを使用して実装されています)、事前に作成された実装を見つけることができる場合があります。そうでない場合、このアルゴリズムは非常に簡単に実装できます。そのための疑似コードを次に示します。

for each index i = 0 to n - 1, inclusive:
    choose a random index j in the range i to n - 1, inclusive.
    swap A[i] and A[j]

これを実装するときは、ランダム インデックスを選択するときに、0 から n-1 までの範囲のインデックスを選択しないように注意してください。これにより、文字の不均一な分布が生じます (これについては、この以前の質問で詳しく読むことができます)。

お役に立てれば！

Answer 2

Knuth Shuffle (別名、Fisher-Yates Shuffle) を使用します。セットのすべての順列の可能性が等しくなるようにするという望ましい機能があります。 これは、任意のサイズのオブジェクトで動作する C での実装 (および他の言語での実装) へのリンクです。