生成无重复的随机数

Question

我想生成不重复的随机数，直到全部消失，然后再次使用初始数据集生成随机数。

我知道将已经生成的数字保存在一个数组中并循环遍历它们以检查它是否已经生成或从数组中扣除生成的数字并使用新数组随机化数字的方法。

我要的不是那些方法，如果有一种高效利用数据结构的方法就好了，如果是其他方法也可以

谢谢

Answer 1

我不确定您使用的是什么语言，但这里有一些 C++ 代码可以满足您的需求。它不是搜索数组，而是直接检查内存的特定部分是否设置了标志，如果未设置，则选择的数字是新的并打印出来。

我标记为处理程序的部分是找到唯一编号时首先执行的代码。如果您想要一组更大的随机数，请将 10 和 11 更改为不同的数字，但您可能必须永远等待输出。

int main(int argc, char *argv[]){
char randn[10];
char randnset[10];
int n;
int ct=0;
memset(randnset,'1',10);
memset(randn,0,10);
while (ct < 10){
    srand(time(NULL));
    n=rand() % 11;
    if (!randn[n]){
        printf("%d\n",n); // handler
        randn[n]='1';
        ct++;
    }
}
return 0;
}

Answer 2

每个随机生成器函数都将种子值作为参数，并在其内部算法中使用它来生成随机数。如果要生成相同的数字序列，则必须使用相同的种子值。例如，您可以像这样在 Java 中实现此目的：

int seed = 10;
Random r = new Random(seed);
for(int i=0; i<10; i++){
    System.out.println(r.nextInt());
}

输出是这样的（当然在你的系统中会有不同的结果）：

-1157793070
1913984760
1107254586
1773446580
254270492
-1408064384
1048475594
1581279777
-778209333
1532292428

每次执行它都会给我相同的结果。

Answer 3

假设您想生成 1,000 个唯一的随机数并将它们一次一个地呈现给某个代码。当你用完这些数字时，你想再次显示相同的数字，但顺序不同。

要生成数字，请使用散列 table。在 C# 中，它看起来像这样：

const int MaxNumbers = 1000;
HashSet<int> uniqueNumbers = new HashSet<int>();
Random rnd = new Random();
// generate random numbers until there are 1000 in the hash table
while (uniqueNumbers.Count < MaxNumbers)
{
    uniqueNumbers.Add(rnd.Next());
}
// At this point you have 1,000 unique random numbers
// Put them in an array
int[] myNumbers = uniqueNumbers.ToArray();

之所以有效，是因为 HashSet.Add 方法拒绝重复。而且速度非常快，因为在散列 table 中查找是 O(1).

现在，您可以通过将当前索引设置为 0 来为它们提供服务，并在每次请求数字时递增它。类似于：

int ixCurrent = 0;
int GetNextNumber()
{
    if (ixCurrent < MaxNumbers)
    {
        ++ixCurrent;
        return myNumbers[ixCurrent-1];
    }

但是当 ixCurrent 跑到数组末尾时怎么办？输入 Fisher-Yates Shuffle:

    // out of numbers. Shuffle the array and return the first one.
    for (int i = MaxNumbers-1; i > 0; --i)
    {
        int j = rnd.Next(i+1);
        int temp = myNumbers[i];
        myNumbers[i] = myNumbers[j];
        myNumbers[j] = temp;
    }
    ixCurrent = 1;
    return myNumbers[0];
}

如果你知道你想要return的数字在一个特定的范围内（即你想要return随机排列的数字0-999），那么你只需填写一个值为 0-999 的数组并将其打乱。

生成无重复的随机数

Generate random numbers without repeats

arrays

random

data-structures