シャッフルされたリストをその場で O(1) メモリで出力するアルゴリズム

Question

読んだあと この質問 私は次のように疑問に思い始めました。元のリストを変更またはコピーしないシャッフル アルゴリズムを使用することは可能ですか?

明確にするために：

オブジェクトのリストが与えられたと想像してください。リストのサイズは任意ですが、かなり大きい (たとえば、10,000,000 項目) と仮定します。リストの項目をランダムな順序で印刷する必要があり、それをできるだけ早く行う必要があります。ただし、次のことは行わないでください。

• 元のリストをコピーします。これは非常に大きく、コピーすると大量のメモリが浪費されるためです (おそらく使用可能な RAM の制限に達します)。
• 元のリストは何らかの方法で並べ替えられており、後で他の部分が並べ替えに依存するため、元のリストを変更します。
• インデックス リストを作成します。このリストも非常に大きく、コピーには多くの時間とメモリが必要になるためです。(説明:これは、元のリストと同じ数の要素を持つ他のリストを意味します)。

これは可能でしょうか?

追加した： さらなる説明。

1. すべての順列が同じ確率で真のランダムな方法でリストをシャッフルしたいと考えています (もちろん、最初に適切な Rand() 関数があることが前提です)。
2. 元のリストと同じ数の要素を持つポインターのリスト、インデックスのリスト、またはその他のリストを作成するという提案は、元の質問では明らかに非効率的であると見なされます。必要に応じて追加のリストを作成できますが、元のリストよりも大幅に小さくする必要があります。
3. 元のリストは配列のようなもので、O(1) のインデックスによってそこから任意の項目を取得できます。(そのため、目的の項目に到達するためにリストを反復処理する必要がある、二重リンクのリストはありません。)

2を追加しました:OK、次のようにしましょう。1 TB HDD には、それぞれ 512 バイトの大きさ (単一セクター) のデータ項目が詰まっています。すべてのアイテムをシャッフルしながら、このすべてのデータを別の 1TB HDD にコピーしたいとします。これをできるだけ高速に実行する必要があります (データの単一パスなど)。512MB の RAM が利用可能ですが、スワップは考慮しません。(これは理論上のシナリオであり、実際にはこのようなシナリオはありません。完璧なアルゴリズムを見つけたいだけです。)

Answer 1

ここで何PRNGスキームが働くことができないという非常に単純な証拠はあります：

  

PRNGのアイデアは、2つの段階があります。まず、PRNGとその初期状態を選択します。二、出力をシャッフルするPRNGを使用しています。さて、のNがあります！の可能な順列、あなたはのN、少なくとも必要があるので！の異なる可能なスタート状態、フェーズ2を入力すると、これは、フェーズ2の開始時に、あなたがしなければならないことを意味します少なくとも許可されていない状態の ₂ N！のビットを、ログがあります。

しかし、これはそれが行くようなアルゴリズムは、環境から新しいランダムビットを受信スキームを排除しません。 、たとえば、その初期状態は、のレイジーの、まだを繰り返さないことが保証されて読み込み、PRNGがあるかもしれません。私たちはそこではないことを証明することはできますか？

私たちは、完璧なシャッフルアルゴリズムを持っていると仮定します。我々はそれを実行を開始し、それが途中で終了したとき、私たちはコンピュータをスリープ状態に想像してみてください。今、プログラムの完全な状態がどこかに保存されています。 のS はプログラムがこの中間点で内なる可能性のあるすべての状態の集合とする。

アルゴリズムが正しいと終了することが保証されているためには、機能があるのF の保存されたプログラムの状態を加えたビットのいずれかに十分な長さの文字列を与えられ、ディスク読み込みの有効なシーケンスを生成し、完成書き込みます、シャッフル。コンピュータ自体は、この機能を実装しています。しかし、数学関数としてそれを考慮します：

F （ビット×S）の→配列が読み取りおよび書き込み

次に、自明、関数が存在する G の、与えられたのみの保存されたプログラム状態、読み書きがまだディスク・ロケーションのセットを生成します。 （以下、単に、結果を見て、 F のビットのいくつかの任意の文字列を渡す。）

G ののS の→は読み書きする場所の設定の

証拠の残りのビットは、 G 少なくとも <サブ> N C <サブ> N / 2 <含むドメインのことを示すことです/ em>の異なるセットに関係なく、アルゴリズムの選択の。それが本当ならば、そこにのS のうち少なくともその多くの要素でなければならず、そのプログラムの状態は、少なくとものログ ₂ <サブ> N <含まれている必要があります/サブ> C <サブ> N / 2 の要件に違反する途中の時点でビット

私は、しかし、その最後のビットを証明するかどうかはわかりません。のいずれかの型セットの場所、読み、またはの型セットの場所から-to-書き込みアルゴリズムに応じて、低エントロピーであることができます。私は結び目を切ることができ、情報理論のいくつかの明白な原則があります疑い。希望の誰かにこのコミュニティのwikiをマークすると、それを供給します。

Answer 2

まあそれは、すべてのshufflingsはとして考えられるべきである、または配布が偏っことができシャッフルを除き、乱数のどのようなあなたは、すなわち上のビットを依存します。

Pは0..N-1に0..N-1から、このような順列であれば、あなただけの0からNまでのxを繰り返すことができるように、N個の整数の「ランダムに見える」順列を生成するために、数学的な方法があります。 -1及び代わりLの出力リストアイテムL（P（X））（x）とあなたがシャッフルを得ました。そのような置換は、例えば、得られます合同算術を使用しました。 Nが素数である場合、例えば、P（x）=（Xの* k）はMOD Nは任意の0

これは、べき乗剰余は、多くの暗号アルゴリズム（例えばRSA、ディフィー・ヘルマン）の基礎であり、分野の専門家によって強く擬似ランダム動作であると考えられることに留意すべきである。

（素数を必要としない）もう一つの簡単な方法は、Nの代わりにあなたはMだから例えばN.上記の二つの最も力あるM考えるようにドメインを展開する最初のものですN = 12場合は、M = 16を設定します。その後、例えば、全単射ビット演算を使用します。

P(x) = ((x ^ 0xf) ^ (x << 2) + 3) & 0xf

次に、あなたのリストにあなたが出力、あなたは0からM-1までのxと出力L（P（X））を反復処理するときP（x）は、実際に

「真、公平ランダム」溶液を暗号強いブロック暗号（例えばAES）及びランダム鍵（K）を固定した後、シーケンスを繰り返すことによって構築することができる

AES(k, 0), AES(k, 1), ...

とこれが（内部メモリは、暗号によって必要とされる）一定の間隔で行うことができ、AES（K、I）

Answer 3

あなたは、コピーを作成し、それを変更するか、またはあなたが訪問したどの要素を追跡するために許可されていませんか？私はつもりだ、それは可能ではないと言います。私はあなたの第三の基準を誤解していない限ります。

私は、それはあなたがあなたが対応する要素を印刷してきたときにtrueに設定され、10,000,000対応するブール値の配列を作る、と言って許されていない意味するために取ります。そして、あなたは、10,000,000インデックスのリストを作るリストをシャッフルし、その順序で要素をプリントアウトすることができていない。

Answer 4

これら10,000,000アイテムは、そうあなたのリストは、その大きさではありません、実際のアイテムへの参照のみ（またはポインタ）です。そのリストの内部変数のすべての参照+サイズのための32ビットアーキテクチャでのみ〜40メガバイトあなたの項目が基準サイズよりも小さい場合は、あなただけのリスト全体をコピーします。

Answer 5

これを行うことはできません 本当に 乱数ジェネレーターは次のいずれかを行う必要があるためです。

• どの数値がすでに選択されているかを記憶し、それらをスキップします (これにはブール値の O(n) リストが必要で、スキップする数値が増えるにつれて実行時間は徐々に悪化します)。または
• 選択するたびにプールを減らします (元のリストを変更するか、別の O(n) リストを変更する必要があります)。

あなたの質問にはどちらも可能性がないので、「いいえ、それはできません」と言わざるを得ません。

この場合、使用する値のビット マスクを使用する傾向がありますが、前述したように、使用する値が蓄積するにつれて実行時間が悪化するため、スキップは使用しません。

ビット マスクは、元のリストの 39Gb (1,000 万ビットは約 1.2M にすぎません) よりも大幅に優れており、それでも O(n) であるにもかかわらず、要求よりもはるかに小さくなります。

実行時の問題を回避するには、毎回乱数を 1 つだけ生成し、関連する「使用済み」ビットがすでに設定されている場合は、該当するビットが見つかるまでビット マスクを前方にスキャンします。 ない セット。

つまり、乱数発生器がまだ使用されていない番号を取得するのに必死になってぶらぶらする必要はありません。実行時間は、1.2M のデータをスキャンするのにかかる時間と同じくらい悪くなります。

もちろん、これは、いつでも選択される特定の数値が、すでに選択されている数値に基づいて偏っていることを意味しますが、それらの数値はとにかくランダムであるため、偏りはランダムです（そして、数値が そうではなかった 最初から本当にランダムであれば、歪みは問題になりません)。

もう少し多様性が必要な場合は、検索方向を変更することもできます (上または下にスキャン)。

結論:あなたが求めていることが実現可能だとは思えませんが、私の妻がすぐに何度も証言しているように、私は以前にも間違っていたことがあるということを覚えておいてください :-) しかし、すべてのことと同様、通常はそのような問題を回避する方法があります。問題。

Answer 6

それは不可能に聞こえるます。

しかし、10,000,000 64ビット・ポインタは、唯一の76メガバイトについてです。

Answer 7

リニア・フィードバック・シフト・レジスタは、あなたが望むものをほとんど行うことができます - いくつかの限界まで番号のリストを生成しますが、（合理的）ランダムな順序で。それが生成するパターンは、は、あなたがトライランダム性から期待するものと統計的に類似しているが、は、それは暗号化された安全にも、近くではありません。バーレカンプ・マッセイアルゴリズムを使用すると、出力シーケンスに基づいて同等のLFSRをリバースエンジニアリングすることができます。

〜10,000,000アイテムのリストのためのあなたの必要性を考えると、あなたは24ビットの最大長LFSRをしたい、と単純にあなたのリストのサイズよりも大きい出力を破棄したい。

何が価値があるのは、LFSRは、同期間の典型的な線形合同PRNGに比べ、一般的に非常に高速であるため。ハードウェアでは、LFSRは、非常にの単純であるNビットのレジスタで構成される、及びM 2入力XORの（Mは、タップの数である - 時々だけカップル、およびより稀より半ダースかそこら）。

Answer 8

十分なスペースがあれば、

、あなたは、配列内のノードのポインタを格納ビットマップを作成し、次の選択項目を指すランダムint型を得ることができます。すでに選択した場合はアイテムが残っていないまで、そして、1を（左または右、あなたがそれをランダム化することができます）に最も近いを取得（あなたは、ビットマップにすることを保存する）。

何の十分なスペースがありません場合は、あなたがノードのポインタを保存せずに同じことを行うことができますが、時間が（それは時空のトレードオフ☺ます）低下します。

Answer 9

あなたは擬似乱数を作成することができ、ブロック暗号を使用して順列を「確保」 - <のhref = "http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Secure-見ます順列-と-ブロック暗号ここを」REL = "nofollowをnoreferrer">。これらのキーの洞察力は、nビット長のブロック暗号与え、あなたはM

Answer 10

基本的に何が必要正確に一度、各0..N-1の数字を生成乱数ジェネレータです。

ここで中途半端なアイデアです：あなたはその後、そのため乗法群でのmod pは、P-1である1とp-1の間のランダムのx（ピックを選ぶ、nよりもわずかに大きい素数pを選ぶことによってかなりよく行うことができますものは、x ^私を満たすランダムXSとテスト！= 1、私は、p-1を<ために、あなただけのものを見つける前に、いくつかをテストする必要があります）。 Xは、グループを生成しているので、ちょうど1のX ^ I MOD Pを計算する<= I <= P-2及びそれを使用するP-2 2及びP-1の間に明確な（ISH）乱数を与えます。 > 2を減算したものを捨てる= nと、それはあなたを印刷するインデックスのシーケンスを与えます。

このひどくランダムではありませんが、（1）上記指標を取って、同じ手法を複数回使用することができますし、別の発電機×2の指数としてそれらを使用して、あなたが必要となります（別のプライムP2を法のn