创build没有重复的随机数字序列
重复：
O（1）中唯一的随机数？
我想要一个伪随机数发生器，可以随机生成没有重复的数字。
例如：
随机（10）
可能会返回5，9，1，4，2，8，3，7，6，10
有没有更好的方法来做到这一点，除了使数字的范围和洗牌，或检查生成的列表重复？
编辑：
另外我希望它能够在没有整个范围的情况下生成大数字。
编辑：
我看到每个人都build议洗牌algorithm。 但是如果我想产生一个大的随机数（1024字节+），那么这个方法会占用更多的内存，比我只使用一个普通的RNG并插入一个Set直到它是一个指定的长度，对不对？ 有没有更好的mathalgorithm。
您可能对线性反馈移位寄存器感兴趣。 我们过去用硬件来构build这些，但我也是用软件来完成的。 它使用一个移位寄存器，其中一些位被异或并反馈到input，如果你select正确的“tap”，你可以得到一个和寄存器一样长的序列。 也就是说，一个16位的lfsr可以产生长度为65535的序列，不需要重复。 这是统计随机的，但当然是可重复的。 另外，如果做错了，你可以得到一些令人尴尬的短序列。 如果你查看lfsr，你会发现如何正确构build它们的例子（也就是说，“最大长度”）。
洗牌是一个非常好的方法来做到这一点（假设你没有引入使用朴素algorithm的偏见）。 见Fisher-Yates shuffle 。
为了确保列表不重复，必须保留以前返回的数字列表。 因为它必须在algorithm结束时生成整个列表，所以在生成有序列表然后洗牌时的存储要求是相同的。
更多关于洗牌的信息： 从有序列表中创build一个随机的有序列表
但是，如果随机数的范围非常大，但所需的数量很less（您已经暗示这是注释中的实际需求），那么生成一个完整的列表并且洗牌是浪费的。 在一个巨大的arrays上洗牌涉及访问虚拟内存的页面（按照定义）将击败操作系统的分页系统（在较小的规模上，与CPU的内存caching相同的问题）。
在这种情况下，search这个列表将会更有效率。 所以理想的是使用启发式（由实验决定）为给定的参数select正确的实现。 （道歉在C＃而不是C ++，但ASFAC ++ B的例子，我正在训练自己思考在C＃）。
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; } 检查重复数字的成本，碰撞时的循环成本等都将是昂贵的，但是可能会有一些Threshold值，其速度比分配给整个范围要快。
对于足够小的数量要求，由于更大的局部性，更低的开销，比较的便宜性，使用数组可以更快地使用数组并进行线性search。
同样对于大量和大范围，可能最好是根据请求返回产生序列中数字的对象，而不是预先为结果分配数组。 这在C＃中非常容易实现，这要归功于yield return关键字：
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; } }
如果一个随机数保证不会重复，那么随机数会随着数字的产生而减less（ random(10)数random(10)数random(10)是相当可预测的，甚至在只有8个数的情况下有50-50的机会）。
我知道tou不想在大范围洗牌，因为你必须存储整个列表才能这样做。
相反，使用可逆的伪随机哈希。 然后依次input数值0 1 2 3 4 5 6等。
有这样的无限数量的哈希值。 如果限制在2的权力，他们不会太难产生，但是可以使用任何基础。
这里有一个例子，如果你想通过所有2 ^ 32 32位值。 这是最简单的写法，因为在这种情况下，隐式mod 2 ^ 32的整数运算对您有利。
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; }
如果您不介意平庸的随机性属性，并且如果元素的数量允许，那么您可以使用线性同余随机数生成器 。
洗牌是最好的，你可以做一个特定的范围内随机数字没有重复。 您所描述的方法（随机生成数字并将它们放入Set中，直到达到指定长度）的原因效率不高，原因是重复。 从理论上讲，该algorithm可能永远不会完成。 最好的情况是，它将在一个无限的时间内完成，相比之下，随机播放将总是以高度可预测的时间进行。
回应编辑和评论：
如果您在评论中指出数字的范围非常大，并且您希望随机select相对较less的数字而不重复，那么重复的可能性会迅速减less。 范围和select数量之间的大小差异越大，重复select的可能性越小，并且在问题中描述的select和检查algorithm的性能会越好。
怎么样使用GUID生成器（就像在.NET中）。 当然不能保证不会有重复，但是获得一个的几率很低。
这已经被问到过 – 请参阅我对上一个问题的回答 。 简而言之：您可以使用分组密码在您想要的任何范围内生成安全（随机）排列，而不必在任何位置存储整个排列。
如果你想创build大的（比如说，64位或更大的）随机数而不重复，那就创build它们。 如果你使用的是一个好的随机数发生器，那实际上有足够的熵，那么产生重复的几率就会很小，不值得担心。
例如，当生成encryption密钥时，实际上没有人会检查他们之前是否生成了相同的密钥; 既然你信任你的随机数生成器，那么一个专门的攻击者将无法获得相同的密钥，那么为什么你会期望你不小心拿出了同样的密钥呢？
当然，如果你有一个糟糕的随机数生成器（比如Debian的SSL随机数生成器漏洞 ），或者生成的数字太小， 生日悖论会给你一个很高的碰撞机会，那么你需要做一些事情来确保你不会重复。 但是对于具有良好生成器的大型随机数字，只要信任概率不会给你任何重复。
在生成您的号码时，请使用布隆filter来检测重复项。 这将使用最less量的内存。 系列中根本不需要存储更早的数字。
权衡是你的列表不能在你的范围内详尽无遗。 如果你的数字真的在256 ^ 1024的数量级，那几乎没有任何折衷。
（当然，如果它们在这个尺度上实际上是随机的，那么即使是检测重复也是浪费时间，如果地球上的每一台计算机都产生了万亿亿次的随机数，微不足道。）
我第二个gbarry关于使用LFSR的答案。 即使在软件中实现它们也是非常有效和简单的，并且保证不会在具有N位移位寄存器的LFSR的（2 ^ N-1）用途中重复。
但是有一些缺点：通过观察来自RNG的less量输出，可以重buildLFSR并预测它将产生的所有值，使得它们不能用于密码学，并且在任何地方都需要好的RNG。 第二个问题是，根据LFSR实现，全零字或全部（字节）字是无效的。 与你的问题相关的第三个问题是，LFSR产生的最大数量总是2 – 1（或2 – 2的幂）的幂。
根据您的应用程序，第一个缺点可能不是问题。 从你给的例子来看，你似乎并不期望在答案中是零。 所以，第二个问题似乎与你的情况不相关。 最大值（因而范围）的问题可以通过重用LFSR来解决，直到你得到一个范围内的数字。 这是一个例子：
假设你想有1到10之间的数字（如你的例子）。 您将使用一个范围[1，15]的4位LFSR。 这里是一个伪代码，如何获取范围[1,10]中的数字：
x = LFSR.getRandomNumber(); while (x > 10) { x = LFSR.getRandomNumber(); }
您应该将以前的代码embedded到您的RNG中; 这样调用者就不会在乎实现了。 请注意，如果使用较大的移位寄存器，则会降低RNG，并且所需的最大数量不是2 – 1的乘方。
对N个元素进行混洗不会占用过多的内存……考虑一下。 一次只能交换一个元素，所以使用的最大内存是N + 1个元素。
假设你有一个随机或伪随机数字发生器，即使它不能保证返回唯一值，你可以实现一个返回唯一值每次使用这个代码，假设上限保持不变（即你总是调用它random(10) ，不要random(10); random(11)调用random(10); random(11) 。
该代码不检查错误。 你可以自己添加，如果你想。
如果你想要大范围的数字，它也需要大量的内存。
/* 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; }
假设您想要生成一连串256个随机数字而不重复。
- 创build一个用零初始化的256位（32字节）内存块，我们称之为
b - 您的循环variables将是
n，即尚未生成的数字的数量 - 从
n = 256循环到n = 1 - 在
[0, n)范围内生成一个随机数r - 在内存块
bfind第r个零位，我们称之为p - 将
p放在结果列表中，一个名为q的数组 - 将存储器块
b的p位翻转为1 - 在
n = 1通过之后，您完成了您的数字列表
下面是我刚刚讨论的一个简短例子，最初使用n = 4：
**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]
请检查答案
按照随机顺序生成整数序列，而不需要预先构build整个列表
也是我的答案就在那里
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.
我之前问过一个类似的问题，但是我的整个范围的int请参阅查找散列函数/有序的Int / to / Shuffled Int /
static std::unordered_set<long> s; long l = 0; for(; !l && (s.end() != s.find(l)); l = generator()); v.insert(l);
generator（）是你的随机数发生器。 只要条目不在您的设置中，您就会滚动数字，然后添加您在其中find的内容。 你明白了。
我做了很长时间的例子，但是如果你的PRNG是模板化的，你应该创build一个模板。
另一种方法是使用一个密码安全的PRNG，这个PRNG的产生两次相同的数字的概率非常低。
如果您不是指生成的序列的统计特性较差，则有一种方法：
假设您要生成N个数字，每个数字都是1024位。 你可以牺牲一些生成的数字是“反”。
所以你生成每个随机数，但是你select了一些位，把二进制编码的计数器（从variables，你每增加一个下一个随机数生成）。
你可以把这个数字分成一个比特，并把它放在生成数字的一些不太重要的位上。
这样你就可以确保你每次都得到唯一的号码。
我的意思是，例如，每个生成的数字如下所示：xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxyyxxxxyxyyyyxxyxx其中x是直接从生成器中获取的，ys是从计数器variables中获取的。
梅森扭转者
其中的描述可以在这里find维基百科： 梅森扭转者
查看页面底部的各种语言的实现。
问题是从范围1..M中selectN个唯一数字的“随机”序列，其中N和M之间的关系没有约束（M可以大得多，大约相同，甚至小于N;他们可能不是主要的）。
在线性反馈移位寄存器上的扩展答案：对于一个给定的M，构造一个最大的LFSR，用于比M大的两个最小的幂。然后，从LFSR中剔除大于M的数字。平均而言，抛出最多一半的生成数（因为通过构build的LFSR的范围的一半以上小于M），所以得到一个数的预期运行时间是O（1）。 您不存储以前生成的数字，因此空间消耗也是O（1）。 如果在获得N个数字之前循环，那么M小于N（或者LFSR构造不正确）。
您可以在这里find最大长度为168位的最大长度LFSR参数（来自维基百科）： http : //www.xilinx.com/support/documentation/application_notes/xapp052.pdf
这里有一些Java代码：
/ ** *在[0，M）中生成一个唯一的“随机”数字序列* @author dkoes * * /
公共类UniqueRandom {long lfsr; 长面具 长时间以来
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; }
}
这个答案提出了一些策略来获得你想要的，并使用一些已知的algorithm来确保它们是随机的。
Fisher-Yates shufflealgorithm的内部版本叫做Durstenfeld版本，在装入数组或集合时随机分配顺序获取的项目到数组和集合中。
有一点要记住的是，加载时使用的Fisher-Yates（AKA Knuth）shuffle或Durstenfeld版本对于对象数组是高效的，因为只有对象的引用指针被移动，对象本身不必作为algorithm的一部分进行检查或与任何其他对象进行比较。
我将在下面给出两个algorithm。
如果你想要真正巨大的随机数，大约在1024个字节以上，那么一个非常好的随机生成器可以一次生成无符号的字节或单词。 随机地产生尽可能多的字节或字，因为你需要构造数字，把它变成一个带有引用指针的对象，嘿，你有一个非常大的随机整数。 如果您需要一个特定的范围，您可以将一个零字节的基本值添加到字节序列的低位末端以将值向上移。 这可能是你最好的select。
如果你需要消除真正巨大的随机数字的重复，那就更棘手了。 即使是真正巨大的随机数字，删除重复也使他们显着偏见，而不是随机的。 如果你有一大堆不真实的庞大的随机数，而你随机select那些尚未被选中的数，那么这种偏见只会造成巨大数值的巨大偏差。 Durstenfeld版本的Yates-Fisher的逆向版本可以用来随机地从一大组数据中select数值，将它们从剩余的数值中删除，并将它们插入到一个新的数组中，这与源和目标arrays就地。 这将是非常有效的。
这可能是一个很好的策略，从一个非常大的一组，他们没有重复获得巨大的价值的随机数。 只需在源集合中选取一个随机位置，获取其值，将其值与源集合中的顶层元素进行交换，将源集合的大小减小1，然后使用缩小的源集合重复，直到您select了足够的值。 这是Durstenfeld版本的Fisher-Yates的反面。 然后，您可以使用Fisher-Yatesalgorithm的Dursenfeld版本将获取的值插入到目标集合中。 然而，这是过度的，因为它们应该随机select，并按照这里给出的随机sorting。
两种algorithm都假定您有一些随机数实例方法nextInt（int setSize），它会生成从零到setSize的随机整数，这意味着有setSize可能值。 在这种情况下，由于数组的最后一个索引是size-1，因此它将是数组的大小。
第一种algorithm是Fisher-Yates（又名Knuth）shufflealgorithm的Durstenfeld版本，适用于任意长度的数组，将从0到数组长度的整数随机排列到数组中。 该数组不必是一个整数数组，但可以是任何依次获取的对象的数组，这实际上使它成为一个引用指针数组。 它简单，简短，非常有效
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
瞧，你现在已经有一个随机数组了。
如果你想随机洗一个你已经有的数组，这里是标准的Fisher-Yatesalgorithm。
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
对于sorting的集合和集合，即某种types的列表对象，您可以使用添加/或插入索引值，允许您在任何地方插入项目，但必须允许在当前最后一项之后添加或追加，以避免造成偏见在随机化。
这是一种随机而不重复的结果。 它也适用于string。 它在C＃中，但logig应该在很多地方工作。 把随机结果放在一个列表中，并检查新的随机元素是否在列表中。 如果不是，你有一个新的随机元素。 如果在该列表中，则重复该随机操作，直到获得不在该列表中的元素。
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和myshufflefunction，我在此慷慨地委托给其他人:)
其实，这里有一个小点。 不允许重复的随机数发生器不是随机的。
有非重复的随机数字，并避免检查双打数字，并反复得到新的数字wavingtime使用下面的方法，以确保最小的兰德使用：例如，如果你想得到100非重复随机数：1。用1到100的数字填充一个数组2.使用Rand函数在（1-100）范围内得到一个随机数3.使用生成的随机数作为索引从数组中获得th值（Numbers [IndexGeneratedFromRandFunction] 4 。将数组中的数字移到左边5.从第2步开始重复，但现在响起应该是（1-99）并继续
现在我们有一个数组不同的数字！
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; } }
