C++ 无重复的随机数组生成
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20734774/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Random array generation with no duplicates
提问by user3128016
I am trying to create something that generates a random array with no duplicate values. I've already looked at other answers but none seem to help me understand. I cannot think of a way to actually generate random numbers that contain no duplicates. Here is what i have tried so far:
我正在尝试创建一些可以生成没有重复值的随机数组的东西。我已经看过其他答案，但似乎没有一个能帮助我理解。我想不出一种方法来实际生成不包含重复项的随机数。这是我迄今为止尝试过的：
srand(time(NULL));
int numbers [4];
for (int x=0; x!=4;x++)
{
numbers[x] = 1 + (rand() % 4) ;
printf("%d ", numbers[x]);
}
Any help will be appreciated.
任何帮助将不胜感激。
回答by Darklighter
You start off filling a container with consecutive elements beginning at 0
您开始使用从以下位置开始的连续元素填充容器 0
std::iota(begin(vec), end(vec), 0);
std::iota(begin(vec), end(vec), 0);
then you get yourself a decent random number generator and seed it properly
然后你得到一个像样的随机数生成器并正确播种
std::mt19937 rng(std::random_device{}());
std::mt19937 rng(std::random_device{}());
finally you shuffle the elements using the rng
最后你使用 rng 对元素进行洗牌
std::shuffle(begin(vec), end(vec), rng);
std::shuffle(begin(vec), end(vec), rng);
On some implementations random_devicedoesn't work properly (most notably gcc on windows) and you have to use an alternative seed, i.e. the current time → chrono.
在某些实现random_device中无法正常工作（最明显的是 Windows 上的 gcc），您必须使用替代种子，即当前时间 → chrono。
回答by rullof
First of all rand()is generatig random numbers but not wihout duplicates.
首先rand()是生成随机数但不是没有重复。
If you want to generate a random array without duplicatesthe rand()method is not working at all.
如果您想生成一个没有重复的随机数组，则该rand()方法根本不起作用。
Let say you want to generatean array of 1000 numbers. In the best case let say you generated the first 999 numbers without duplicates and last think to do is generatingthe last number. The probability of getting that number is 1/1000so this is almost going to take forever to get generated. In practice only 10 numbers makes a big trouble.
假设您要生成一个包含1000 个数字的数组。在最好的情况下，比方说您生成的第一个999号没有重复，并最后想到做的是产生的最后一个数字。获得这个数字的概率是 1/1000，所以这几乎需要很长时间才能生成。实际上，只有 10 个数字会带来很大的麻烦。
The best method is to generate all your numbers by incrementation (or strictly monotonic sequence) is shufflethem. In this case there will be no duplicates
最好的方法是通过递增（或严格单调序列）生成所有数字，然后将它们打乱。在这种情况下不会有重复
Hereis an exemple on how to do it with 10 numbers. Even with 1000 numbers it's working.
这是一个关于如何使用 10 个数字进行操作的示例。即使有 1000 个数字，它也能正常工作。
Note: Suffle function from Jhon Leehey's answer.
注意：来自Jhon Leehey的回答的Suffle 函数。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void shuffle(int *arr, size_t n)
{
if (n > 1)
{
size_t i;
srand(time(NULL));
for (i = 0; i < n - 1; i++)
{
size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
int t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
}
int main()
{
int i;
int arr[10];
for (i=0; i<10; i++){
arr[i] = i;
}
shuffle(arr, 10);
for (i=0; i<10; i++){
printf("%d ", arr[i]);
}
}
回答by Paul92
There are 2 solutions to choose from:
有两种解决方案可供选择：
Generate random numbers using something like rand() and check for duplicates.
Find a mathematical sequence that is strictly monotonic (preferably strictly increasing) and get its terms as members of your array. Then, you can shuffle your array. The result will not be truly random, but neither using rand() won't. rand() uses a simillar tehnique, and that is why we need to set the seed with something changeing, like time. You can use time for example to generate the first element of the sequence, and with a good sequence your results will be at least decent. Note that the sequence MUST be strictly monotonic, to avoid generation of duplicates. The sequence need not be too complex. For example, if you get unix timemodulo 10000 as the first term and then you generate other terms using a reccurence like x[i] = x[i-1] + 3*x[i-2] should be fine. Of course, you may use more sophisticated sequences too, but be careful at overflow (as you can't apply modulo operator to the result, because it would not be increasing anymore) and the number of digits you would like to have.
使用 rand() 之类的方法生成随机数并检查重复项。
找到一个严格单调（最好是严格递增）的数学序列，并将其项作为数组的成员。然后，你可以洗牌你的数组。结果不会是真正随机的，但使用 rand() 也不会。rand() 使用类似的技术，这就是为什么我们需要用一些变化的东西来设置种子，比如时间。例如，您可以使用 time 来生成序列的第一个元素，如果序列良好，您的结果至少会不错。请注意，序列必须严格单调，以避免产生重复。顺序不必太复杂。例如，如果您获得unix 时间modulo 10000 作为第一项，然后使用像 x[i] = x[i-1] + 3*x[i-2] 这样的重复生成其他项应该没问题。当然，您也可以使用更复杂的序列，但要小心溢出（因为您不能对结果应用模运算符，因为它不会再增加）和您想要的位数。
回答by Edge7
srand(time(NULL));
const int N = 4;
int numbers [N];
bool isAlreadyAdded(int value, int index)
{
for( int i = 0; i < index; i ++)
if( numbers[i] == value)
return true;
return false;
}
for (int x=0; x!=N;x++)
{
int tmp = 1 + (rand() % N) ;
while( x !=0 && isAlreadyAdded(tmp, x))
tmp = 1 + (rand() % N) ;
numbers[x] = tmp;
printf("%d ", numbers[x]);
}
It's just a way. it should work, of course there are better ways
这只是一种方式。它应该有效，当然有更好的方法
回答by Zoran Horvat
You can use your own random number generator which has the sequence greater or equal to length of the array. Refer to http://en.wikipedia.org/wiki/Linear_congruential_generator#Period_lengthfor instructions.
您可以使用自己的随机数生成器，它的序列大于或等于数组的长度。有关说明，请参阅http://en.wikipedia.org/wiki/Linear_congruential_generator#Period_length。
So you need LCG with expression Xn+1 = (aXn + c) mod m. Value m must be at least as large as length of the array. Check "if and only if" conditions for maximum sequence length and make sure that your numbers satisfy them.
所以你需要表达式 Xn+1 = (aXn + c) mod m 的 LCG。值 m 必须至少与数组的长度一样大。检查最大序列长度的“当且仅当”条件，并确保您的数字满足它们。
As a result, you will be able to generate random numbers with satisfactory randomness for most uses, which is guaranteed to not repeat any number in the first m calls.
因此，对于大多数用途，您将能够生成具有令人满意的随机性的随机数，这保证在前 m 次调用中不会重复任何数字。
回答by Keith
In c++, all you need is:
在 C++ 中，您只需要：
std::random_shuffle()
http://www.cplusplus.com/reference/algorithm/random_shuffle/
http://www.cplusplus.com/reference/algorithm/random_shuffle/
int numbers [4];
for (int x=0; x!=4;x++)
{
numbers[x] = x;
}
std::random_shuffle(numbers, numbers +4);
Update: OK, I had been thinking that a suitable map function could go from each index to a random number, but thinking again I realize that may be hard. The following should work:
更新：好的，我一直在想一个合适的映射函数可以从每个索引到一个随机数，但再想一想我意识到这可能很难。以下应该工作：
int size = 10;
int range = 100;
std::set<int> sample;
while(sample.size() != size)
sample.insert(rand() % range); // Or whatever random source.
std::vector<int> result(sample.begin(), sample.end());
std::random_shuffle ( result.begin(), result.end() );
回答by Bryan Polyak
After you generate each random number, loop through the previous values and compare. If there's a match, re-generate a new value and try again.
生成每个随机数后，循环遍历之前的值并进行比较。如果匹配，请重新生成新值并重试。
回答by Fiddling Bits
How about this:
这个怎么样：
#define NUMS (10)
int randomSequence[NUMS] = {0}, i = 0, randomNum;
bool numExists[NUMS] = {false};
while(i != NUMS)
{
randomNum = rand() % NUMS;
if(numExists[randomNum] == false)
{
randomSequence[i++] = randomNum;
numExists[randomNum] = true;
}
}
Of course, the bigger NUMSis, the longer it will take to execute the whileloop.
当然，越大NUMS，执行while循环所需的时间就越长。
回答by ibtaylor
If you want to pseudo-randomly traverse a large space without maintaining visited indices, you should look at this project I contributed to years ago for the basic technique. http://packetfactory.openwall.net/projects/ipspace/index.html
如果你想伪随机地遍历一个大空间而不维护访问过的索引，你应该看看我多年前贡献的这个项目的基本技术。http://packetfactory.openwall.net/projects/ipspace/index.html
You should be able to adapt it to your purposes, source is at the bottom of the page.
您应该能够根据您的目的对其进行调整，来源位于页面底部。
