C - 生成没有重复的随机序列，无需改组

Question

我想以随机顺序生成序列 [0...1'000'000] 的数组无需改组。

这意味着我不想做:

int arr[1000000];

for (int i = 0; i < 1000000; i++)
{
    arr[i] = i; 
}

shuffle(arr);
shuffle(arr);

我想弄清楚如何在没有“黑盒”shuffle 功能的情况下做到这一点。我也不想在 1 和 1'000'000 之间随机选择一个索引，因为在数字 999'999 只有 1/1'000'000 机会继续。

我一直在想一个解决方案，我认为关键是并行数组并向后循环，然后使用模数来限制您尚未访问过的索引，但我不能保证我得到的值(value)是独一无二的。

我也不想使用 HashSet 或 TreeSet 实现。

Answer 1

这可以在 O(n) 时间内完成，有两个列表，一个按数字(初始)顺序排列，另一个按结果顺序排列。

您在源列表中按顺序从 n 元素开始。然后选择一个随机数 mod n。这为您提供了下一个元素，您将其放置在目标列表中。

现在是关键部分。如果您每次都在 0 和 n-1 之间选择一个随机数，就像您认为洗牌所做的那样，您选择一个数字的机会就会增加选之前。那么你如何处理呢？通过减少可供选择的可用数字列表。

在源列表中，选择一个数字后，将列表的最后一个元素移动到刚刚使用的索引处。您现在有一个 n-1 号码列表可供选择。因此，在下一次迭代中，您采用随机数模 n-1。继续，直到您的源列表只有一个元素。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LEN 10

int main()
{
    int a[LEN], b[LEN];
    int i, val;
    int count = LEN;

    srand(time(NULL));

    for (i=0;i<LEN;i++) {
        a[i]=i+1;
    }
    for (i=0;i<LEN;i++) {
        val = rand() % count;
        b[i] = a[val];
        a[val] = a[count-1];
        count--;
    }
    for (i=0;i<LEN;i++) {
        printf("%d ", b[i]);
    }
    printf("\n");

    return 0;
}

编辑:

这是一个稍微更高效的版本，它不使用两个数组，因此是 O(1) 空间:

int a[LEN];
int i, val, tmp;

srand(time(NULL));

for (i=0;i<LEN;i++) {
    a[i]=i+1;
}
for (i=0;i<LEN-1;i++) {
    val = (rand() % (LEN - 1 - i)) + i + 1;
    tmp = a[i];
    a[i] = a[val];
    a[val] = tmp;
}
for (i=0;i<LEN;i++) {
    printf("%d ", a[i]);
}
printf("\n");