创build没有重复的随机数字序列

O（1）中唯一的随机数？

编辑：

``IEnumerable<int> GenerateRandomNumbers(int range, int quantity) { int[] a = new int[quantity]; if (range < Threshold) { for (int n = 0; n < range; n++) a[n] = n; Shuffle(a); } else { HashSet<int> used = new HashSet<int>(); for (int n = 0; n < quantity; n++) { int r = Random(range); while (!used.Add(r)) r = Random(range); a[n] = r; } } return a; }` `

` `IEnumerable<int> ForLargeQuantityAndRange(int quantity, int range) { for (int n = 0; n < quantity; n++) { int r = Random(range); while (!used.Add(r)) r = Random(range); yield return r; } }` `

` `unsigned int reversableHash(unsigned int x) { x*=0xDEADBEEF; x=x^(x>>17); x*=0x01234567; x+=0x88776655; x=x^(x>>4); x=x^(x>>9); x*=0x91827363; x=x^(x>>7); x=x^(x>>11); x=x^(x>>20); x*=0x77773333; return x; }` `

（当然，如果它们在这个尺度上实际上是随机的，那么即使是检测重复也是浪费时间，如果地球上的每一台计算机都产生了万亿亿次的随机数，微不足道。）

` `x = LFSR.getRandomNumber(); while (x > 10) { x = LFSR.getRandomNumber(); }` `

` `/* the function returns a random number between 0 and max -1 * not necessarily unique * I assume it's written */ int random(int max); /* the function returns a unique random number between 0 and max - 1 */ int unique_random(int max) { static int *list = NULL; /* contains a list of numbers we haven't returned */ static int in_progress = 0; /* 0 --> we haven't started randomizing numbers * 1 --> we have started randomizing numbers */ static int count; static prev_max = 0; // initialize the list if (!in_progress || (prev_max != max)) { if (list != NULL) { free(list); } list = malloc(sizeof(int) * max); prev_max = max; in_progress = 1; count = max - 1; int i; for (i = max - 1; i >= 0; --i) { list[i] = i; } } /* now choose one from the list */ int index = random(count); int retval = list[index]; /* now we throw away the returned value. * we do this by shortening the list by 1 * and replacing the element we returned with * the highest remaining number */ swap(&list[index], &list[count]); /* when the count reaches 0 we start over */ if (count == 0) { in_progress = 0; free(list); list = 0; } else { /* reduce the counter by 1 */ count--; } } /* swap two numbers */ void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; }` `

1. 创build一个用零初始化的256位（32字节）内存块，我们称之为`b`
2. 您的循环variables将是`n` ，即尚未生成的数字的数量
3. `n = 256`循环到`n = 1`
4. `[0, n)`范围内生成一个随机数`r`
5. 在内存块`b`find第`r`个零位，我们称之为`p`
6. `p`放在结果列表中，一个名为`q`的数组
7. 将存储器块`b``p`位翻转为`1`
8. `n = 1`通过之后，您完成了您的数字列表

` `**Setup** b = 0000 q = [] **First loop pass, where n = 4** r = 2 p = 2 b = 0010 q = [2] **Second loop pass, where n = 3** r = 2 p = 3 b = 0011 q = [2, 3] **Third loop pass, where n = 2** r = 0 p = 0 b = 1011 q = [2, 3, 0] ** Fourth and final loop pass, where n = 1** r = 0 p = 1 b = 1111 q = [2, 3, 0, 1]` `

` ` very simple random is 1+((power(r,x)-1) mod p) will be from 1 to p for values of x from 1 to p and will be random where r and p are prime numbers and r <> p.` `

` `static std::unordered_set<long> s; long l = 0; for(; !l && (s.end() != s.find(l)); l = generator()); v.insert(l);` `

generator（）是你的随机数发生器。 只要条目不在您的设置中，您就会滚动数字，然后添加您在其中find的内容。 你明白了。

/ ** *在[0，M）中生成一个唯一的“随机”数字序列* @author dkoes * * /

` `private static long seed = 1; //indexed by number of bits private static int [][] taps = { null, // 0 null, // 1 null, // 2 {3,2}, //3 {4,3}, {5,3}, {6,5}, {7,6}, {8,6,5,4}, {9,5}, {10,7}, {11,9}, {12,6,4,1}, {13,4,3,1}, {14,5,3,1}, {15,14}, {16,15,13,4}, {17,14}, {18,11}, {19,6,2,1}, {20,17}, {21,19}, {22,21}, {23,18}, {24,23,22,17}, {25,22}, {26,6,2,1}, {27,5,2,1}, {28,25}, {29,27}, {30,6,4,1}, {31,28}, {32,22,2,1}, {33,20}, {34,27,2,1}, {35,33}, {36,25}, {37,5,4,3,2,1}, {38,6,5,1}, {39,35}, {40,38,21,19}, {41,38}, {42,41,20,19}, {43,42,38,37}, {44,43,18,17}, {45,44,42,41}, {46,45,26,25}, {47,42}, {48,47,21,20}, {49,40}, {50,49,24,23}, {51,50,36,35}, {52,49}, {53,52,38,37}, {54,53,18,17}, {55,31}, {56,55,35,34}, {57,50}, {58,39}, {59,58,38,37}, {60,59}, {61,60,46,45}, {62,61,6,5}, {63,62}, }; //m is upperbound; things break if it isn't positive UniqueRandom(long m) { max = m; lfsr = seed; //could easily pass a starting point instead //figure out number of bits int bits = 0; long b = m; while((b >>>= 1) != 0) { bits++; } bits++; if(bits < 3) bits = 3; mask = 0; for(int i = 0; i < taps[bits].length; i++) { mask |= (1L << (taps[bits][i]-1)); } } //return -1 if we've cycled long next() { long ret = -1; if(lfsr == 0) return -1; do { ret = lfsr; //update lfsr - from wikipedia long lsb = lfsr & 1; lfsr >>>= 1; if(lsb == 1) lfsr ^= mask; if(lfsr == seed) lfsr = 0; //cycled, stick ret--; //zero is stuck state, never generated so sub 1 to get it } while(ret >= max); return ret; }` `

}

Fisher-Yates shufflealgorithm的内部版本叫做Durstenfeld版本，在装入数组或集合时随机分配顺序获取的项目到数组和集合中。

` `int size = someNumber; int[] int array = new int[size]; // here is the array to load int location; // this will get assigned a value before used // i will also conveniently be the value to load, but any sequentially acquired // object will work for (int i = 0; i <= size; i++) { // conveniently, i is also the value to load // you can instance or acquire any object at this place in the algorithm to load // by reference, into the array and use a pointer to it in place of j int j = i; // in this example, j is trivially i if (i == 0) { // first integer goes into first location array[i] = j; // this may get swapped from here later } else { // subsequent integers go into random locations // the next random location will be somewhere in the locations // already used or a new one at the end // here we get the next random location // to preserve true randomness without a significant bias // it is REALLY IMPORTANT that the newest value could be // stored in the newest location, that is, // location has to be able to randomly have the value i int location = nextInt(i + 1); // a random value between 0 and i // move the random location's value to the new location array[i] = array[location]; array[location] = j; // put the new value into the random location } // end if...else } // end for` `

` `type[] array = new type[size]; // some code that loads array... // randomly pick an item anywhere in the current array segment, // swap it with the top element in the current array segment, // then shorten the array segment by 1 // just as with the Durstenfeld version above, // it is REALLY IMPORTANT that an element could get // swapped with itself to avoid any bias in the randomization type temp; // this will get assigned a value before used int location; // this will get assigned a value before used for (int i = arrayLength -1 ; i > 0; i--) { int location = nextInt(i + 1); temp = array[i]; array[i] = array[location]; array[location] = temp; } // end for` `

` `List<string> Erledigte = new List<string>(); private void Form1_Load(object sender, EventArgs e) { label1.Text = ""; listBox1.Items.Add("a"); listBox1.Items.Add("b"); listBox1.Items.Add("c"); listBox1.Items.Add("d"); listBox1.Items.Add("e"); } private void button1_Click(object sender, EventArgs e) { Random rand = new Random(); int index=rand.Next(0, listBox1.Items.Count); string rndString = listBox1.Items[index].ToString(); if (listBox1.Items.Count <= Erledigte.Count) { return; } else { if (Erledigte.Contains(rndString)) { //MessageBox.Show("vorhanden"); while (Erledigte.Contains(rndString)) { index = rand.Next(0, listBox1.Items.Count); rndString = listBox1.Items[index].ToString(); } } Erledigte.Add(rndString); label1.Text += rndString; } }` `

` `const size_t amount = 100; // a limited amount of random numbers vector<long int> numbers; numbers.reserve( amount ); const short int spread = 250; // about 250 between each random number numbers.push_back( myrandom( spread ) ); for( int n = 0; n != amount; ++n ) { const short int increment = myrandom( spread ); numbers.push_back( numbers.back() + increment ); } myshuffle( numbers );` `

`myrandom``myshuffle`function，我在此慷慨地委托给其他人:)

` `int main() { int b[(the number if them)]; for (int i = 0; i < (the number of them); i++) { int a = rand() % (the number of them + 1) + 1; int j = 0; while (j < i) { if (a == b[j]) { a = rand() % (the number of them + 1) + 1; j = -1; } j++; } b[i] = a; } }` `