繰り返されない（つまり、6が2回表示されない）0から1000までの一意の乱数を生成したいのですが、それを行うために前の値のO（N）検索のようなものに頼ることはありません。これは可能ですか？
dicroce
質問する
104510 次
22 に答える
257
1001 個の整数の配列を 0 ～ 1000 の値で初期化し、変数 max を配列の現在の最大インデックス (1000 から開始) に設定します。0 から max の間の乱数 r を選び、位置 r の数を位置 max の数と交換し、位置 max の数を返します。max を 1 減らして続行します。max が 0 の場合、max を配列のサイズ - 1 に戻して、配列を再初期化する必要なくやり直します。
更新: 質問に答えたときにこの方法を思いつきましたが、いくつかの調査の結果、これはDurstenfeld-Fisher-Yates または Knuth-Fisher-Yates として知られるFisher-Yatesの修正版であることがわかりました。説明が少しわかりにくいかもしれないので、以下に例を示します (1001 の代わりに 11 の要素を使用)。
配列は、array[n] = n に初期化された 11 個の要素から始まり、最大値は 10 から始まります。
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+--+
^
max
各反復で、乱数 r が 0 と max の間で選択され、array[r] と array[max] が交換され、新しい array[max] が返され、max がデクリメントされます。
max = 10, r = 3
+--------------------+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
+--+--+--+--+--+--+--+--+--+--+--+
max = 9, r = 7
+-----+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
+--+--+--+--+--+--+--+--+--+--+--+
max = 8, r = 1
+--------------------+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+
max = 7, r = 5
+-----+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+
...
11 回の反復の後、配列内のすべての数値が選択され、最大 == 0 になり、配列要素がシャッフルされます。
+--+--+--+--+--+--+--+--+--+--+--+
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+
この時点で、最大値を 10 にリセットしてプロセスを続行できます。
于 2008-10-12T20:57:02.080 に答える
72
あなたはこれを行うことができます：
- 0..1000のリストを作成します。
- リストをシャッフルします。（これを行うための良い方法については、Fisher-Yatesシャッフルを参照してください。）
- シャッフルされたリストから順番に番号を返します。
したがって、これは毎回古い値を検索する必要はありませんが、それでも最初のシャッフルにはO（N）が必要です。しかし、ニルスがコメントで指摘したように、これは償却されたO（1）です。
于 2008-10-12T20:37:24.413 に答える
63
最大線形フィードバック シフト レジスタを使用します。
数行の C で実装可能であり、実行時には、いくつかのテスト/分岐、少しの追加、およびビット シフトを行うだけです。ランダムではありませんが、ほとんどの人はだまされます。
于 2008-10-14T18:14:59.677 に答える
28
Format-Preserving Encryptionを使用してカウンターを暗号化できます。カウンターは 0 から上に向かって進み、暗号化は選択したキーを使用して、任意の基数と幅の一見ランダムな値に変換します。たとえば、この質問の例: 基数 10、幅 3。
通常、ブロック暗号のブロック サイズは 64 ビットまたは 128 ビットなどに固定されています。しかし、フォーマット保持暗号化を使用すると、AES のような標準的な暗号を使用して、必要な基数と幅のより狭い幅の暗号を、依然として暗号学的に堅牢なアルゴリズムで作成できます。
衝突が発生しないことが保証されています (暗号化アルゴリズムが 1:1 マッピングを作成するため)。また、可逆 (双方向マッピング) であるため、結果の数値を取得して、開始時のカウンター値に戻すことができます。
この手法は、シャッフルされた配列などを格納するためのメモリを必要としないため、メモリが限られているシステムでは利点となります。
AES-FFXは、これを実現するために提案されている標準的な方法の 1 つです。完全に準拠しているわけではありませんが、AES-FFX のアイデアに基づいた基本的な Python コードをいくつか試してみました。Pythonコードはこちら を参照してください。たとえば、カウンターをランダムに見える 7 桁の 10 進数または 16 ビットの数値に暗号化できます。質問が述べたように、基数10、幅3（0から999までの数値を与えるため）の例を次に示します。
000 733
001 374
002 882
003 684
004 593
005 578
006 233
007 811
008 072
009 337
010 119
011 103
012 797
013 257
014 932
015 433
... ...
繰り返しのないさまざまな疑似ランダム シーケンスを取得するには、暗号化キーを変更します。各暗号化キーは、異なる繰り返しのない疑似ランダム シーケンスを生成します。
于 2013-04-19T04:33:02.900 に答える
23
A Linear Congruential Generatorを使用できます。ここでm(モジュラス) は 1000 より大きい最も近い素数になります。範囲外の数値を取得したら、次の数値を取得します。シーケンスは、すべての要素が発生したときにのみ繰り返され、テーブルを使用する必要はありません。ただし、このジェネレーターの欠点 (ランダム性の欠如を含む) に注意してください。
于 2008-10-12T21:46:14.460 に答える
8
0...1000 のような小さい数値の場合、すべての数値を含むリストを作成してシャッフルするのは簡単です。しかし、取得する数値のセットが非常に大きい場合は、別のエレガントな方法があります。キーと暗号化ハッシュ関数を使用して疑似乱数順列を構築できます。次の C++ 風の疑似コードの例を参照してください。
unsigned randperm(string key, unsigned bits, unsigned index) {
unsigned half1 = bits / 2;
unsigned half2 = (bits+1) / 2;
unsigned mask1 = (1 << half1) - 1;
unsigned mask2 = (1 << half2) - 1;
for (int round=0; round<5; ++round) {
unsigned temp = (index >> half1);
temp = (temp << 4) + round;
index ^= hash( key + "/" + int2str(temp) ) & mask1;
index = ((index & mask2) << half1) | ((index >> half2) & mask1);
}
return index;
}
ここでhashは、文字列をおそらく巨大な符号なし整数にマップする任意の疑似乱数関数を示します。この関数randpermは、固定キーを想定した 0...pow(2,bits)-1 内のすべての数値の順列です。変数を変更するすべてのステップは元に戻すことができるため、これは構成からindex導き出されます。これはFeistel 暗号に着想を得たものです。
于 2010-06-22T15:11:01.657 に答える
6
Linear congruential generatorが最も簡単な解決策だと思います。
a、c、m の値には 3 つの制限しかありません
- mとcは互いに素であり、
- a-1はmのすべての素因数で割り切れます
- mが 4 で割り切れる場合、 a-1は4で割り切れる
PSメソッドはすでに言及されていましたが、投稿には定数値に関する間違った仮定があります。以下の定数は、あなたのケースではうまくいくはずです
あなたの場合、、、を使用a = 1002できc = 757ますm = 1001
X = (1002 * X + 757) mod 1001
于 2016-12-17T04:22:27.257 に答える
5
これを解決するために配列は必要ありません。
ビットマスクとカウンターが必要です。
カウンターをゼロに初期化し、連続する呼び出しでインクリメントします。カウンターとビットマスク (起動時にランダムに選択されるか、固定されたもの) を XOR して、疑似乱数を生成します。1000 を超える数値を使用できない場合は、9 ビットを超えるビットマスクを使用しないでください。(つまり、ビットマスクは 511 を超えない整数です。)
カウンターが 1000 を超えたら、必ずゼロにリセットしてください。この時点で、必要に応じて別のランダムなビットマスクを選択して、同じ一連の数値を異なる順序で生成できます。
于 2009-01-03T05:55:29.303 に答える
3
この方法は、制限が高く、少数の乱数のみを生成する場合に適しています。
#!/usr/bin/perl
($top, $n) = @ARGV; # generate $n integer numbers in [0, $top)
$last = -1;
for $i (0 .. $n-1) {
$range = $top - $n + $i - $last;
$r = 1 - rand(1.0)**(1 / ($n - $i));
$last += int($r * $range + 1);
print "$last ($r)\n";
}
数字は昇順で生成されますが、後でシャッフルすることができます。
于 2012-01-19T18:19:36.347 に答える
3
これは、最初のソリューションのロジックを使用する、私が入力したコードです。これが「言語にとらわれない」ことは知っていますが、誰かが迅速な実用的な解決策を探している場合に備えて、これを C# の例として提示したかっただけです。
// Initialize variables
Random RandomClass = new Random();
int RandArrayNum;
int MaxNumber = 10;
int LastNumInArray;
int PickedNumInArray;
int[] OrderedArray = new int[MaxNumber]; // Ordered Array - set
int[] ShuffledArray = new int[MaxNumber]; // Shuffled Array - not set
// Populate the Ordered Array
for (int i = 0; i < MaxNumber; i++)
{
OrderedArray[i] = i;
listBox1.Items.Add(OrderedArray[i]);
}
// Execute the Shuffle
for (int i = MaxNumber - 1; i > 0; i--)
{
RandArrayNum = RandomClass.Next(i + 1); // Save random #
ShuffledArray[i] = OrderedArray[RandArrayNum]; // Populting the array in reverse
LastNumInArray = OrderedArray[i]; // Save Last Number in Test array
PickedNumInArray = OrderedArray[RandArrayNum]; // Save Picked Random #
OrderedArray[i] = PickedNumInArray; // The number is now moved to the back end
OrderedArray[RandArrayNum] = LastNumInArray; // The picked number is moved into position
}
for (int i = 0; i < MaxNumber; i++)
{
listBox2.Items.Add(ShuffledArray[i]);
}
于 2010-08-25T17:49:40.260 に答える
2
public static int[] randN(int n, int min, int max)
{
if (max <= min)
throw new ArgumentException("Max need to be greater than Min");
if (max - min < n)
throw new ArgumentException("Range needs to be longer than N");
var r = new Random();
HashSet<int> set = new HashSet<int>();
while (set.Count < n)
{
var i = r.Next(max - min) + min;
if (!set.Contains(i))
set.Add(i);
}
return set.ToArray();
}
N 反復しない乱数は、必要に応じて O(n) の複雑さになります。
注: ランダムは、スレッド セーフが適用された状態で静的である必要があります。
于 2012-05-23T19:43:18.360 に答える
2
10 ビットの優れた疑似乱数ジェネレーターを使用して、1001 から 1023 を破棄し、0 から 1000 を残すことができます。
ここから、10 ビット PRNG の設計を取得します。
10 ビット、フィードバック多項式 x^10 + x^7 + 1 (周期 1023)
ガロア LFSR を使用して高速なコードを取得する
于 2009-01-03T10:25:23.003 に答える
2
シャッフルされたリストを何度も見直したいとしましょうO(n)。最初からシャッフルするたびに遅延が発生することはありません。その場合、次のようにすることができます。
0 から 1000 までの 2 つのリスト A と B を作成すると、
2nスペースが必要になります。Fisher-Yates を使用したリスト A のシャッフルには
n時間がかかります。数字を引くときは、もう一方のリストで 1 ステップのフィッシャー イェーツ シャッフルを行います。
カーソルがリストの最後にあるとき、別のリストに切り替えます。
前処理
cursor = 0
selector = A
other = B
shuffle(A)
描く
temp = selector[cursor]
swap(other[cursor], other[random])
if cursor == N
then swap(selector, other); cursor = 0
else cursor = cursor + 1
return temp
于 2016-04-27T20:33:16.183 に答える
1
別の可能性：
フラグの配列を使用できます。そして、それがすでに選択されているときに次のものを取ります。
ただし、1000回の呼び出し後は関数が終了しないことに注意してください。そのため、安全策を講じる必要があります。
于 2008-10-12T20:38:25.660 に答える
1
ここでの回答のほとんどは、同じ数値を 2 回返さないことを保証できません。正しい解決策は次のとおりです。
int nrrand(void) {
static int s = 1;
static int start = -1;
do {
s = (s * 1103515245 + 12345) & 1023;
} while (s >= 1001);
if (start < 0) start = s;
else if (s == start) abort();
return s;
}
制約が適切に指定されているかどうかはわかりません。1000 の他の出力の後に値の繰り返しが許可されていると想定していますが、1000 のセットの最後と最初に両方が表示される限り、単純に 0 の直後に 0 が続くことを許可しています。繰り返しの間に 1000 の他の値を使用すると、その制限の外で発生した他の値がないため、シーケンスが毎回まったく同じ方法で再生される状況が強制されます。
値を繰り返す前に、少なくとも 500 個の他の値を常に保証するメソッドを次に示します。
int nrrand(void) {
static int h[1001];
static int n = -1;
if (n < 0) {
int s = 1;
for (int i = 0; i < 1001; i++) {
do {
s = (s * 1103515245 + 12345) & 1023;
} while (s >= 1001);
/* If we used `i` rather than `s` then our early results would be poorly distributed. */
h[i] = s;
}
n = 0;
}
int i = rand(500);
if (i != 0) {
i = (n + i) % 1001;
int t = h[i];
h[i] = h[n];
h[n] = t;
}
i = h[n];
n = (n + 1) % 1001;
return i;
}
于 2015-06-02T04:32:42.903 に答える
1
N が 1000 よりも大きく、K 個のランダム サンプルを描画する必要がある場合、これまでのサンプルを含むセットを使用できます。描画ごとに拒否サンプリングを使用します。これは「ほぼ」O(1) 操作になるため、合計実行時間は O(N) ストレージでほぼ O(K) になります。
このアルゴリズムは、K が N に「近い」場合に衝突します。これは、実行時間が O(K) よりもはるかに悪いことを意味します。簡単な解決策は、ロジックを逆にして、K > N/2 の場合、まだ描画されていないすべてのサンプルの記録を保持することです。抽出ごとに、棄却セットからサンプルが削除されます。
拒否サンプリングのもう 1 つの明らかな問題は、それが O(N) ストレージであることです。N が数十億以上の場合、これは悪いニュースです。しかし、その問題を解決するアルゴリズムがあります。このアルゴリズムは発明者の名をとってヴィッターのアルゴリズムと呼ばれています。アルゴリズムはここで説明されています。Vitter のアルゴリズムの要点は、各描画の後、一様なサンプリングを保証する特定の分布を使用してランダム スキップを計算することです。
于 2016-11-22T08:26:07.297 に答える
0
https://stackoverflow.com/a/46807110/8794687で私の回答をご覧ください
これは、平均時間複雑度O ( s log s )を持つ最も単純なアルゴリズムの 1 つです。sはサンプル サイズを示します。また、複雑さがO ( s )であると主張されているハッシュ テーブル アルゴリズムへのリンクもいくつかあります。
于 2017-10-30T05:02:32.410 に答える
-1
誰かが「Excelで乱数を作成する」を投稿しました。私はこの理想を使っています。str.index と str.ran の 2 つの部分で構造を作成します。10 個の乱数の場合、10 個の構造体の配列を作成します。str.index を 0 から 9 に設定し、str.ran を別の乱数に設定します。
for(i=0;i<10; ++i) {
arr[i].index = i;
arr[i].ran = rand();
}
arr[i].ran の値で配列をソートします。str.index はランダムな順序になりました。以下はcコードです：
#include <stdio.h>
#include <stdlib.h>
struct RanStr { int index; int ran;};
struct RanStr arr[10];
int sort_function(const void *a, const void *b);
int main(int argc, char *argv[])
{
int cnt, i;
//seed(125);
for(i=0;i<10; ++i)
{
arr[i].ran = rand();
arr[i].index = i;
printf("arr[%d] Initial Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
}
qsort( (void *)arr, 10, sizeof(arr[0]), sort_function);
printf("\n===================\n");
for(i=0;i<10; ++i)
{
printf("arr[%d] Random Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
}
return 0;
}
int sort_function(const void *a, const void *b)
{
struct RanStr *a1, *b1;
a1=(struct RanStr *) a;
b1=(struct RanStr *) b;
return( a1->ran - b1->ran );
}
于 2019-11-01T21:32:31.463 に答える