不思議なKnuthトランプアルゴリズム
3533 ワード
目次
•前に書く
•公平なランダムアルゴリズム?
•Knuthアルゴリズム
•考え方の証明
•前に書く
ランダムアルゴリズムといえば、私たちの頭の中には多くの解決策が現れるかもしれません(ps:解決策が思いつかないのは、random関数がたくさん使われているのかもしれませんが、ハハハ)が、私がここで話しているKnuthランダムアルゴリズムは、私が初めて接触した後、感嘆せざるを得ません.確かに不思議ですが、その不思議なところはこのアルゴリズムがどれだけ深く、実現がどれだけ複雑なのかではありません.このアルゴリズムの思想は極めて簡単で、核心コードまで2行で、芸術的な思想は公平なランダムアルゴリズムを実現した.アルゴリズムは簡単で、なぜ無視されやすいのか、アルゴリズムの本質から考えたいと思っています.アルゴリズムを理解するだけでなく、なぜ私たちがこんなにすばらしいアルゴリズムを考えられなかったのか、収穫があると信じています.
•公平なランダムアルゴリズム?
私たちが正式にKnuthアルゴリズムを説明する前に、私はまずこの問題を考えるべきだと思います.もしあなたが面接に出会ったら、面接官はあなたに公平なトランプアルゴリズムを設計させたいと思っています.あなたはどのように設計しますか.問題は、一連の数(配列)をランダムに順番を乱し、randomを得意とする私たちが、最初に思いついたのは、すべてのカードを1つの配列に入れて、2枚のカードを交換するたびに、ランダムにk回取ればいいということかもしれません.考えはとても无邪気で可爱くて、それではランダムkはこの时具体的に何回ですか?明らかに、このkを配列要素の数に関連付ける必要があります.このような方法はランダムなkよりも合理的です.そしてこの時私たちは一息ついて、やっとこのアルゴリズムを設計しました.
もしあなたがそう思うならば、それはあまりにも単純で、上で言ったこのアルゴリズムの構想はランダムにトランプを洗う考えで、私たちがトランプを乱すのを助けることができるかもしれません.しかし、私たちは一つの問題を考えて、テーマ自体に戻って「公平なトランプアルゴリズム」を考えなければなりません.実はこれが私たちの多くの人が無視しているポイントで、「公平」なトランプアルゴリズムがこの問題の精髄かもしれません.もし私たちがランダムで公平であることを保証したら?実は数学では私たちがよく言う等確率です.
この時、私たちはすべての要素の配列を列挙することができて、その後ランダムにその中の1つの配列状況を選択することができて、これは完璧に等確率に達して、つまり“公平”です.しかし、このアルゴリズムは本当にいいですか?いいえ、この考え方は等確率を達成しましたが、時間の複雑度が非常に高いので、知っておいてください.n!指数爆発よりも恐ろしい複雑さです.
実は私たちは全配列の考えの上でいくつか啓発を得ることができて、全配列は実はすべての要素がランダムにある位置に現れるためで、この時、私たちは視野を全体の配列から単一の要素に下げて討論することができて、つまり、私たちはすべての要素が確率的に任意の位置に現れることを保証しなければなりません.私たちの言う公平を実現することができます.
•Knuthアルゴリズム
2つの要素を最初にランダムに交換する考え方の下でさらに考えることができ,各位置が各要素を等確率で配置できることをどのように保証するかを考えることができる.実は難しくありません.私たちは配列の最後の要素から前へ循環して、毎回循環して、私たちはランダムに1つの要素と現在の循環のある要素を選んで交換値をすればいいです.このように言うのは直感的ではないかもしれません.私はまずアルゴリズムコードを持ってきて、理解しながら、以下のようにします.
2行のコードしかありません.あなたは間違っていません.あなたの目の前に現れたのは有名なKnuthトランプアルゴリズムです.まず、このサイクルが何をしているのか簡単に理解することができます.実はとても簡単で、iは後ろから前へ、毎回1つの[0...i]の間の下付き文字をランダムにして、それからarr[i]とこのランダムな下付き文字要素、つまりarr[rand()%(i+1)]と位置を交換します.特筆すべきは、毎回ランダムに1つの[0...i]の間の下付き記号であるため、私たちの計算方法はrand()%(i+1)であり、i+1に余分を取り、ランダムなインデックスが[0...i]の間にあることを保証する.
よく理解できるでしょう.では、どこが公平なのかと聞くかもしれません.これは元の考えと同じではありませんか.順番を決めただけだ.違いはもちろん違いますが、確率的な方法でなぜ私たちのアルゴリズムが公平なのかを証明します(確率証明を聞くと怖くないでください.実は簡単です).これもこのアルゴリズムのすばらしさです.
•考え方の証明
まず一つの例を使って、例を見ながら私たちのアルゴリズムを証明します.そうすれば、もっと直感的になります.まず,5つの数字,すなわち1,2,3,4,5を簡単に用いてシミュレーションを行った.最初の5つの数は以下のように並べられていると仮定します.
1
2
3
4
5
では、このアルゴリズムによれば、まずこの5つの要素のうち1つの要素を選択し、最後の要素5と位置を交換し、ランダムに2が出たと仮定し、交換後は以下のようにする.
1
5
3
4
2
この時、私たちは2が最後の位置に現れる確率を計算します.とても簡単で、5つの要素の中から選んだので、1/5です.実際,このステップによれば,任意の要素が最後の位置に現れる確率は,いずれも1/5である.信じない?私たちは次に下を見ます.このアルゴリズムによれば,選択した我々は先に放っておく,すなわちもう2を気にしないで,前の4つの要素のうち,1つの要素をランダムにして,最後から2番目の位置に置く.ランダムに3,3と現在の最後から2番目の位置の要素4が位置を交換すると仮定します(ラベルグレーは選択されないことを意味します).
1
5
4
3
2
では、この時、3がこの位置に現れる確率はどのくらいですか?計算方法は、P=4/5*1/4=1/5
これは、前のフィルタリングで3が選択されていない確率が4/5であるため、確率を計算する簡単な方法である.このラウンドでは、全部で4つの要素があるので、3が選択される確率は1/4です.したがって,最終的には,確率は4／5＊1／4＝1／5である,この最後から2番目の位置に3が現れる.ここで私は次に1ラウンドをシミュレートします.状況は以下の通りです.次に抽選されたのは1です.
4
5
1
3
2
確率計算を行い,1が第1ラウンドで選ばれなかった確率は4／5,第2ラウンドで選ばれなかった確率は3／4,第3ラウンドで選ばれた確率は1／3,最後に計算したP＝4／5＊3／4＊1／3＝1／5であった.
実際,この方法で計算すると,任意の要素がこの逆数の2番目の位置に現れる確率は,いずれも1/5である.あなたは信じないで計算を続けることができます.私はここでシミュレーションをしません.上は例にすぎないが,この証明は配列要素の個数nの任意の配列に容易に拡張でき,アルゴリズム全体の複雑さはO(n)であり,不思議ではないか.しかし、この时、誰かが聞くかもしれませんが、私は行ってから、もちろんいいですが、コードはもっと複雑になりますが、他のことには影響しません.実は、多くのランダムな場所で、使えます.たとえば、掃雷はランダムなディスク面を生成します.掃雷の2次元盤面を先に逐行接続し,1次元と見なすことができる.その後、k個の雷を順番に開始位置に置く.
•前に書く
•公平なランダムアルゴリズム?
•Knuthアルゴリズム
•考え方の証明
•前に書く
ランダムアルゴリズムといえば、私たちの頭の中には多くの解決策が現れるかもしれません(ps:解決策が思いつかないのは、random関数がたくさん使われているのかもしれませんが、ハハハ)が、私がここで話しているKnuthランダムアルゴリズムは、私が初めて接触した後、感嘆せざるを得ません.確かに不思議ですが、その不思議なところはこのアルゴリズムがどれだけ深く、実現がどれだけ複雑なのかではありません.このアルゴリズムの思想は極めて簡単で、核心コードまで2行で、芸術的な思想は公平なランダムアルゴリズムを実現した.アルゴリズムは簡単で、なぜ無視されやすいのか、アルゴリズムの本質から考えたいと思っています.アルゴリズムを理解するだけでなく、なぜ私たちがこんなにすばらしいアルゴリズムを考えられなかったのか、収穫があると信じています.
•公平なランダムアルゴリズム?
私たちが正式にKnuthアルゴリズムを説明する前に、私はまずこの問題を考えるべきだと思います.もしあなたが面接に出会ったら、面接官はあなたに公平なトランプアルゴリズムを設計させたいと思っています.あなたはどのように設計しますか.問題は、一連の数(配列)をランダムに順番を乱し、randomを得意とする私たちが、最初に思いついたのは、すべてのカードを1つの配列に入れて、2枚のカードを交換するたびに、ランダムにk回取ればいいということかもしれません.考えはとても无邪気で可爱くて、それではランダムkはこの时具体的に何回ですか?明らかに、このkを配列要素の数に関連付ける必要があります.このような方法はランダムなkよりも合理的です.そしてこの時私たちは一息ついて、やっとこのアルゴリズムを設計しました.
もしあなたがそう思うならば、それはあまりにも単純で、上で言ったこのアルゴリズムの構想はランダムにトランプを洗う考えで、私たちがトランプを乱すのを助けることができるかもしれません.しかし、私たちは一つの問題を考えて、テーマ自体に戻って「公平なトランプアルゴリズム」を考えなければなりません.実はこれが私たちの多くの人が無視しているポイントで、「公平」なトランプアルゴリズムがこの問題の精髄かもしれません.もし私たちがランダムで公平であることを保証したら?実は数学では私たちがよく言う等確率です.
この時、私たちはすべての要素の配列を列挙することができて、その後ランダムにその中の1つの配列状況を選択することができて、これは完璧に等確率に達して、つまり“公平”です.しかし、このアルゴリズムは本当にいいですか?いいえ、この考え方は等確率を達成しましたが、時間の複雑度が非常に高いので、知っておいてください.n!指数爆発よりも恐ろしい複雑さです.
実は私たちは全配列の考えの上でいくつか啓発を得ることができて、全配列は実はすべての要素がランダムにある位置に現れるためで、この時、私たちは視野を全体の配列から単一の要素に下げて討論することができて、つまり、私たちはすべての要素が確率的に任意の位置に現れることを保証しなければなりません.私たちの言う公平を実現することができます.
•Knuthアルゴリズム
2つの要素を最初にランダムに交換する考え方の下でさらに考えることができ,各位置が各要素を等確率で配置できることをどのように保証するかを考えることができる.実は難しくありません.私たちは配列の最後の要素から前へ循環して、毎回循環して、私たちはランダムに1つの要素と現在の循環のある要素を選んで交換値をすればいいです.このように言うのは直感的ではないかもしれません.私はまずアルゴリズムコードを持ってきて、理解しながら、以下のようにします.
for (int i = n - 1; i >= 0; i--) {
swap(arr[i], arr[rand() % (i + 1)]);
}2行のコードしかありません.あなたは間違っていません.あなたの目の前に現れたのは有名なKnuthトランプアルゴリズムです.まず、このサイクルが何をしているのか簡単に理解することができます.実はとても簡単で、iは後ろから前へ、毎回1つの[0...i]の間の下付き文字をランダムにして、それからarr[i]とこのランダムな下付き文字要素、つまりarr[rand()%(i+1)]と位置を交換します.特筆すべきは、毎回ランダムに1つの[0...i]の間の下付き記号であるため、私たちの計算方法はrand()%(i+1)であり、i+1に余分を取り、ランダムなインデックスが[0...i]の間にあることを保証する.
よく理解できるでしょう.では、どこが公平なのかと聞くかもしれません.これは元の考えと同じではありませんか.順番を決めただけだ.違いはもちろん違いますが、確率的な方法でなぜ私たちのアルゴリズムが公平なのかを証明します(確率証明を聞くと怖くないでください.実は簡単です).これもこのアルゴリズムのすばらしさです.
•考え方の証明
まず一つの例を使って、例を見ながら私たちのアルゴリズムを証明します.そうすれば、もっと直感的になります.まず,5つの数字,すなわち1,2,3,4,5を簡単に用いてシミュレーションを行った.最初の5つの数は以下のように並べられていると仮定します.
1
2
3
4
5
では、このアルゴリズムによれば、まずこの5つの要素のうち1つの要素を選択し、最後の要素5と位置を交換し、ランダムに2が出たと仮定し、交換後は以下のようにする.
1
5
3
4
2
この時、私たちは2が最後の位置に現れる確率を計算します.とても簡単で、5つの要素の中から選んだので、1/5です.実際,このステップによれば,任意の要素が最後の位置に現れる確率は,いずれも1/5である.信じない?私たちは次に下を見ます.このアルゴリズムによれば,選択した我々は先に放っておく,すなわちもう2を気にしないで,前の4つの要素のうち,1つの要素をランダムにして,最後から2番目の位置に置く.ランダムに3,3と現在の最後から2番目の位置の要素4が位置を交換すると仮定します(ラベルグレーは選択されないことを意味します).
1
5
4
3
2
では、この時、3がこの位置に現れる確率はどのくらいですか?計算方法は、P=4/5*1/4=1/5
これは、前のフィルタリングで3が選択されていない確率が4/5であるため、確率を計算する簡単な方法である.このラウンドでは、全部で4つの要素があるので、3が選択される確率は1/4です.したがって,最終的には,確率は4／5＊1／4＝1／5である,この最後から2番目の位置に3が現れる.ここで私は次に1ラウンドをシミュレートします.状況は以下の通りです.次に抽選されたのは1です.
4
5
1
3
2
確率計算を行い,1が第1ラウンドで選ばれなかった確率は4／5,第2ラウンドで選ばれなかった確率は3／4,第3ラウンドで選ばれた確率は1／3,最後に計算したP＝4／5＊3／4＊1／3＝1／5であった.
実際,この方法で計算すると,任意の要素がこの逆数の2番目の位置に現れる確率は,いずれも1/5である.あなたは信じないで計算を続けることができます.私はここでシミュレーションをしません.上は例にすぎないが,この証明は配列要素の個数nの任意の配列に容易に拡張でき,アルゴリズム全体の複雑さはO(n)であり,不思議ではないか.しかし、この时、誰かが聞くかもしれませんが、私は行ってから、もちろんいいですが、コードはもっと複雑になりますが、他のことには影響しません.実は、多くのランダムな場所で、使えます.たとえば、掃雷はランダムなディスク面を生成します.掃雷の2次元盤面を先に逐行接続し,1次元と見なすことができる.その後、k個の雷を順番に開始位置に置く.