2

これから生まれた質問。問題は次のように定式化できます。

m <= nの2つの正の整数nとmが与えられた場合、0からnまでのすべての可能な値を循環してカバーする一連の数値を見つける方法はありますか？

基本的な例として、3をcurrent数値として使用すると、0から3までの数値に対して、次の値を次のように計算できます。

next = (current+3) % 4

これが循環します。例：1-> 0-> 3-> 2-> 1など。私はこの解決策を「チャンス」で見つけましたが、それは一般的でさえあり（(i + n) % (n + 1)どの場合でもn）、数学的に証明することはできません。そして、それは少し明白すぎます。

そのような順列を生成するためのより良い方法はありますか？

4

2 に答える 2

3

共通の素数除数を共有しない任意の数で後続の各数をインクリメントする(n-m+1)と、シーケンスがカバーされます（たとえば、[2-11]3、7、または9ずつインクリメントするシーケンス（10個の数）は機能しますが、2、4、5、6、および8共通の除数（2および/または5）を共有しているためではありません

編集

毎回同じ数ずつ増やしたいと思われるので、シャッフルのアイデアを出しました。最初の要素にmがある真に「ランダムな」シーケンスが必要な場合は、mを取り出して、最初に配置します。しかし、それがどのように役立つかはわかりません。

于 2013-01-16T16:15:15.577 に答える
3

質問で何を参照するつもりなmのか、または「一連の数字」をどのように定義しているのかわかりません）。ただし、数のサイクルを取得する1つの方法は、次の形式の再帰（または反復）を使用することです。

next = f(current)

一部の関数の場合f。たとえば、線形合同RNGは反復を使用します。

x = ( a · x + c ) mod m   where 0 < a, c < m

常に0からm-1までのすべての値を生成するわけではありませんが、特定の状況下では次のように生成されます。

c and m are relatively prime

a - 1 is divisible by every prime factor of m (not including m)

if m is divisible by 4, a - 1 is divisible by 4.

（これはハル・ドーベルの定理です。）

a、c == 1は、任意のmについて上記の基準を満たしていることに注意してください。さらに、mが素数の場合、aとcの任意の値が基準を満たし、mが2の累乗である場合、a == 1mod4およびc==1 modとなるように、基準は任意のa、cによって満たされます。 2.ただし、mの特定の値（例：6）の場合、機能するaの値は1のみです。

これは「ステートレス」とは見なされないかもしれませんが、厳密にステートレスな解決策はないと思います。たとえば、次のような関数を探すことができますf。

f(0), f(1),... f(m-1)

の順列です

0, 1, ..., m-1

f(i)の連続する値を呼び出すことによってサイクルを生成できるようにしますi。iしかし、それはまだ状態です。最後に使用した値を覚えておく必要があるためです。

于 2013-01-16T17:01:49.040 に答える