如何使随机数唯一 [英] How to make Random Numbers unique
问题描述
我正在制作一个随机数发生器。它询问用户希望输入多少个数字。例如，如果输入2，它将生成10到99之间的随机数。我制作了生成器，但是我的问题是数字不是唯一的。
I am making a random number generator. It asks how many digits the user wants to be in the number. for example it they enter 2 it will generate random numbers between 10 and 99. I have made the generator but my issue is that the numbers are not unique.
这是我的码。我不确定为什么没有生成唯一编号。我认为srand（time（null））会做到。
Here is my code. I am not sure why it is not generating unique number. I thought srand(time(null)) would do it.
void TargetGen::randomNumberGen()
{
srand (time(NULL));
if (intLength == 1)
{
for (int i = 0; i< intQuantity; i++)
{
int min = 1;
int max = 9;
int number1 = rand();
if (intQuantity > max)
{
intQuantity = max;
}
cout << number1 % max + min << "\t";
}
}
else if (intLength == 2)
{
for (int i = 0; i<intQuantity; i++)
{
int min = 10;
int max = 90;
int number1 = rand();
if (intQuantity > max)
{
intQuantity = max;
}
cout << number1 % max + min << "\t";
}
}
if (intLength == 3)
{
for (int i = 0; i<intQuantity; i++)
{
int min = 100;
int max = 900;
int number1 = rand();
if (intQuantity > max)
{
intQuantity = max;
}
cout << number1 % max + min << "\t";
}
}
else if (intLength == 4)
{
for (int i = 0; i<intQuantity; i++)
{
int min = 1000;
int max = 9000;
int number1 = rand();
if (intQuantity > max)
{
intQuantity = max;
}
cout << number1 % max + min << "\t";
}
}
if (intLength == 5)
{
for (int i = 0; i<intQuantity; i++)
{
int min = 10000;
int max = 90000;
int number1 = rand();
if (intQuantity > max)
{
intQuantity = max;
}
cout << number1 % max + min << "\t";
}
}
else if (intLength == 6)
{
for (int i = 0; i<intQuantity; i++)
{
int min = 100000;
int max = 900000;
int number1 = rand();
if (intQuantity > max)
{
intQuantity = max;
}
cout << number1 % max + min << "\t";
}
}
if (intLength == 7)
{
for (int i = 0; i<intQuantity; i++)
{
int min = 1000000;
int max = 9000000;
int number1 = rand();
if (intQuantity > max)
{
intQuantity = max;
}
cout << number1 % max + min << "\t";
}
}
else if (intLength == 8)
{
for (int i = 0; i <intQuantity; i++)
{
int min = 10000000;
int max = 89999999;
int number1 = rand();
if (intQuantity > max)
{
intQuantity = max;
}
cout << number1 % max + min << "\t";
}
}
if (intLength == 9)
{
for (int i = 0; i < intQuantity; i++)
{
int min = 100000000;
int max = 900000000;
int number1 = rand();
if (intQuantity > max)
{
intQuantity = max;
}
cout << number1 % max + min << "\t";
}
}
}
好的我以为我想出了一种不用数组的方法，但是在切换到fisher yates方法之前，它不起作用。有人可以告诉我为什么这行不通吗？基本上应该将随机数放入变量numGen中。然后在变量b =到numgen中。只是为了保持numGen过去的状态，所以当循环通过并生成另一个随机数时，它将把它与旧数进行比较，如果不等于旧数，则将其输出。如果它等于旧数字而不是输出而不是输出它，它将使i递减，这样它将在循环中运行而不会完全跳过该数字。但是，当我这样做时，它是无限循环的。我不确定为什么。
Okay so I thought I figured out a way to do this without arrays but It isn't working before I switch to the fisher yates method. Can someone tell me why this isn't working? It is supposed to essentially take the random number put that into variable numGen. Then in variable b = to numgen. Just to hold what numGen used to be so when the loop goes through and generates another random number it will compare it to what the old number is and if it is not equal to it, then it will output it. If it is equal to the old number than rather than outputting it, it will deincrement i so that it will run through the loop without skipping over the number entirely. However, when I do this is infinitely loops. And I am not sure why.
如果（intLength == 1）
{
if (intLength == 1) {
for (int i = 0; i< intQuantity; ++i)
{
int min = 1;
int max = 9;
int number1 = rand();
int numGen = number1 % max + min;
if (intQuantity > max)
{
intQuantity = max;
}
for (int k = 0; k < 1; k++)
{
cout << numGen << "\t";
int b = numGen;
}
int b = numGen;
if (b != numGen )
{
cout << numGen << "\t";
}
else
{
i--;
}
}
}
推荐答案
提示0：
使用 二次残差 ；如果整数 q 与完全平方模 p 相乘，则称为二次余数 p ；即，如果存在整数 x 使得：
Hint 0: Use Quadratic residue from number theory; an integer q is called a quadratic residue modulo p if it is congruent to a perfect square modulo p; i.e., if there exists an integer x such that:
x 2 ≡q（mod p）
x2 ≡ q (mod p)
提示1：
定理：假设p是质数，则x的二次残差是唯一的，只要2x < p。例如：
Hint 1: Theorem: Assuming p is a prime number, the quadratic residue of x is unique as long as 2x < p. For example:
0 2 ≡0（mod 13）
02 ≡ 0 (mod 13)
1 2 ≡1（mod 13）
12 ≡ 1 (mod 13)
2 2 ≡4（mod 13）
22 ≡ 4 (mod 13)
3 2 9（mod 13）
32 ≡ 9 (mod 13)
4 2 ≡3（mod 13）
42 ≡ 3 (mod 13)
5 2 ≡12（mod 13）
52 ≡ 12 (mod 13)
6 2 10（mod 13）
62 ≡ 10 (mod 13)
提示2：
定理：假设p是一个质数，使得p≡3（mod 4），不仅x 2 ％p（即二次余数）对于2x < p，但p-x 2 ％p对于2x> p也是唯一的。例如：
Hint 2: Theorem: Assuming p is a prime number such that p ≡ 3 (mod 4), not only x2%p (i.e the quadratic residue) is unique for 2x < p but p - x2%p is also unique for 2x>p. For example:
0 2 ％11 = 0
1 2 ％11 = 1
12%11 = 1
2 2 ％11 = 4
22%11 = 4
3 2 ％11 = 9
32%11 = 9
4 2 ％11 = 5
42%11 = 5
5 2 ％11 = 3
52%11 = 3
11-6 2 ％11 = 8
11 - 62%11 = 8
11-7 2 ％11 = 6
11 - 72%11 = 6
11-8 2 ％11 = 2
11 - 82%11 = 2
11-9 2 ％11 = 7
11 - 92%11 = 7
11-10 2 ％11 = 10
11 - 102%11 = 10
因此，此方法为我们提供了小于p的整数的完美的1对1置换，其中p可以是任何质数，使得p≡3（mod 4）。
Thus, this method provides us with a perfect 1-to-1 permutation on the integers less than p, where p can be any prime such that p ≡ 3 (mod 4).
提示3：
unsigned int UniqueRandomMapping(unsigned int x)
{
const unsigned int p = 11; //any prime number satisfying p ≡ 3 (mod 4)
unsigned int r = ((unsigned long long) x * x) % p;
if (x <= p / 2) return r;
else return p - r;
}
我不担心输入数字错误（例如超出范围） ）。
I didn't worry about the bad input numbers (e.g. out of the range).
备注
- 对于32位整数，您可以选择最大质数，以使p≡3（mod 4）小于2 32 ，即4294967291。
- 尽管如此，该方法给您一个用于生成随机数的1对1映射，它会遇到聚类问题。
- 为提高上述方法的随机性，请将其与
等其他独特的随机映射方法（例如XOR运算符）结合使用。
- For 32-bit integers, you may choose the largest prime number such that p ≡ 3 (mod 4) which is less than 232 which is 4294967291.
- Even though, this method gives you a 1-to-1 mapping for generating random number, it suffers from the clustering issue.
- To improve the randomness of the aforementioned method, combine it with other unique random mapping methods such as XOR operator.
这篇关于如何使随机数唯一的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
