4
記号{a1、a2、a3、...、ak}の順序付けられたリストを与えられたときに、O（n）時間内に同じシンボルの新しいリストを偏りのないランダムな順序？ 「偏りがない」とは、任意の記号のがある位置に終わる確率を意味します。pは1/kです。配列を無作為に並べ替える
O（1）時間に1-kを含む非バイアス整数を生成することが可能であると仮定します。また、O（1）要素のアクセス/変異が可能であり、O（k）時間内にサイズkの新しいリストを作成することが可能であると仮定する。
特に、私は「生成的」アルゴリズムに興味があります。つまり、O（1）の初期オーバーヘッドを持つアルゴリズムに興味があり、スロットあたりO（1）時間かかるリストの各スロットに対して新しい要素を生成します。
説明したように何の解決策は、問題に存在しない場合、私はまだ、次の方法（および/または他の方法で必要に応じて）の一つ以上で私の制約を満たしていない解決策について知りたい：
- 時間複雑さはO（n）より悪い。
- このアルゴリズムは、シンボルの最終位置に関してバイアスされています。
- このアルゴリズムは生成的ではありません。私はこの問題は、我々は1-kから整数のリストをソートし、次に各整数私のためにすることができるので、ランダムに1-kから整数をソートの問題と同じように見えることを追加する必要があり
新しいリストでは、シンボルaiを生成することができます。
あなたはこれまで考えてきたシャッフルアルゴリズムを教えてください。特定の理由で除外しましたか？ –
@Greg：私は本当に便利なものは何も見つかりませんでしたが、間違ったキーワード（ランダムソート、ランダムソートなど）で検索していたようです。 「ランダム化された順列」を探し、「シャッフル」がより多くの結果を返します。私はまだ何かを生み出すことを見つけていない。 – Cam
Knuthシャッフル*はその用語の定義に従って生成されます。 –