この質問は以前に尋ねられましたが、どれも明確に答えられていなかったので、ここで見つけたすべての情報をまとめてみました. 必要に応じて、自由に別の stackexchange サイトにマージ/移動してください。
これに関連して私が見つけた質問は次のとおりです。
この問題は当初、Interviewstreet Code Sprint として投稿されましたが、現在は練習問題として掲載されています。SPOJ にも移植されています。
問題文は次のとおりです。
N枚のカードをシャッフルするアルゴリズムは次のとおりです。
1) カードを K 個の等しい山に分けます。
2) 一番下の N / K カードは、同じ順序でパイル 1 に属します (最初のパイルの一番下のカードは、パイル 1 の一番下のカードです)。
3) 下から次の N / K 枚のカードはパイル 2 に属し、以下同様です。
4) シャッフルされたパイルの一番上のカードがパイル 1 の一番上のカードです。次のカードはパイル 2 の一番上のカードです。...、シャッフルされたパイルの K 番目のカードがパイル K の一番上のカードです。 (K + 1) 番目のカードは山 1 の一番上にあるカード、(K + 2) 番目は山 2 の一番上にあるカードなどです。
たとえば、N = 6、K = 3 の場合、1 度シャッフルすると、カードのデッキ「ABCDEF」(上から下) の順序は「ECAFDB」に変わります。
N と K が与えられた場合、パイルを元の順序に戻すために必要なシャッフルの最小回数は?
入力: 最初の行には、テスト ケースの数 T が含まれます。次の T 行には、それぞれ N と K の 2 つの整数が含まれます。
出力: 必要な最小数のシャッフルを含むテスト ケースごとに 1 つの T 行を出力します。デッキが元の順序に戻らない場合は、-1 を出力します。
制約:
- K は N の因数になります。
- T <= 10000
- 2 <= K <= N <= 10^9
ネタバレ注意 - 自分で解決したい場合は、以下を読まないでください。
問題は次のように翻訳できます。
N 枚のカードのデッキを最初の順序に戻すために、K-way (完全)インシャッフルを実行する必要がある回数を求めてください。
この問題を解決するために、私は 2 つのアプローチを取りました。頭に浮かんだ最初のアプローチは次のとおりです。
- 最初の順序での位置が与えられると、カードの次の位置が生成される式を見つける
- 式を使用して、最初の山 (サイズは n / k) から各カードをシャッフルして最初の位置に戻す回数を決定します。
- 以前に決定されたシャッフル数の最小公倍数を返します
この解の複雑さは O(n / k + max_number_of_suhffles) です。これが実際の実装です。これの問題は、最大時間を超えることです。そのため、ほぼ一定の時間で数値を取得できる式を探し始めました。
ここで最適化できたのは (たとえば、同じ順列サイクルで計算された値をキャッシュするためにいくつかのマップを使用したなど)、interviewstreet で 3/10 テストに合格することでした。
この実装を見つけました。これは、初期状態に戻るために必要なシャッフルの数が、N + 1 に対する Kの乗法次数であると想定しています。wiki から:
As a consequence of Lagrange's theorem, ordn(a) always divides φ(n).
φ(n) はEuler totient function、ordn は群次数- 私たちが探しているものです。φ を使用してシャッフルの数を計算するこの論文を見つけましたが、これは k-way ではなく 2-way in-shuffle のみを対象としています。
この実装の手順は次のとおりです。
- 素数のリストを事前計算 < 100 000
φ(N+1)その素因数から計算されます。φ(N + 1)は、その素因数をすべての可能な方法で組み合わせることによって、 のすべての因数を決定しました。x各因子を順番に試して、最小のもの を取得します。k ^ x % N + 1 = 1
この実装はGitHub にも投稿されています。
これは非常に高速に実行されますが、自動グレーダーは、SPOJ と Interviewstreet の両方で、10 個のテストのうち 9 個を「不正解」に分類してくれます。
2 つの実装からの出力を比較してみましたが、入れたテストケース (既知の結果とランダム) では、2 つの実装は常に同じものを出力します。これは奇妙です。最初のアルゴリズムが正しいと確信しているので、2 番目のアルゴリズムも正しいはずだと思います。
「間違った答え」の分類は、コードの実行時エラーに起因する可能性がありますが、この原因として考えられるものは何もありません。
数をシャッフルしてもデックを初期状態に戻せない場合は考慮していませんでした。これは不可能であると理解しています。シャッフルの数が非常に多い場合でも、有限数の完全なシャッフルが最終的には最初の順序を復元します。
時間を割いてこれを読んでくれたなら、ありがとう。:) この問題に興味があります。解決したいと思います。