3

要素のリストが与えられた場合、最終的に選択された半分の部分が一方の側にあり、残りがもう一方の側にあることを保証するシャッフルアルゴリズムが存在しますか？

例：{4、3、10、7、2、9、6、8、1、5}

上記のセットを前提として、アルゴリズム自体が「マーク」されているものとされていないものを認識していなくても、最終的にマークされたものを左に移動するミキシングアルゴリズムが必要です。

   {4、3、10、7、2、9、6、8、1、5}
     X X X X X

許容できる結果は次のようになります：
   { 4、10、9、6、1、3、7、2、8、5} {
   1、9、10、4、6、2、8、5、7、3}
   {1、 4、9、10、6、3、7、5、8、2}など

難易度：アルゴリズムは、内容を混合するために乱数を使用するべきではありません。それは反復プロセスでなければなりません。だからフィッシャー-イェーツは出ています。

4

4 に答える 4

4

リストをフラグ付きとフラグなしの2つのリストに分割します。両方のサブリストをシャッフルし、一方にフラグ付き、もう一方にフラグなしを配置し​​ます。これで、任意のシャッフルアルゴを使用できます。

于 2010-07-21T13:54:04.093 に答える
1

あなたstd::next_permutation()が望むものになりますか？（可能なすべての順列を作成するため、最終的には、マークされた1回も左側に配置されます。）

于 2010-07-21T13:51:39.417 に答える
0

のようなものnext_permutationがその仕事をし、（最終的には）ボゴソートのようなものもそうするでしょう。どちらも、最終的には、許容できると考えるすべての順列を含む、すべての可能な順列を生成します（許容できない任意の数とともに）。

ボゴソートは、次のことを示しています。「アルゴリズムは、コンテンツを混合するために乱数を使用するべきではありません。反復プロセスである必要があります。したがって、Fisher-Yatesは出ていません。」誤った二分法です。ボゴソートはランダムに混合され、反復されます。

于 2010-07-21T13:58:49.067 に答える
0

次のようなアルゴリズムを探していると思います。*シャッフルのように見える反復プロセスをユーザーに表示するために使用できます*元のセットが2つの（事前に選択された）グループに分けられますが、各グループ内でランダムに並べられます

私には、このアルゴリズムのグループにマークされた/マークされていない用語を使用して、10個の数字を検討するのに適した単純なものがあるようです。

1. Randomly select two members of the set
2. if swapping these two members would result in a marked number 
     being moved into positions 1-5 then forget about this swap and start again
3. Swap these elements
4. Check if positions 1-5 have ONLY marked elements, 
     if so you are done, otherwise start again

これは、フィッシャー-イェーツのような効率的な統計的に優れたシャッフルを提供しませんが、画面の取り違えをよく見せます。

于 2010-07-21T14:15:03.047 に答える