生成 [0,8000] 范围内 1000 个不同整数的算法？

Question

可能的重复：
怎么做您可以有效地生成一个包含 0 到上限 N 之间的 K 个非重复整数的列表

有哪些替代方法可以生成 [0,8000] 范围内的 1000 个不同的随机整数，而不是以下方法：

1. 朴素方法：生成一个数字并检查它是否已经在数组中。 O(n^2)
2. 线性shuffle：生成序列0到8000，shuffle，取前1000。O(n)

Answer 1

没有排序的排序列表，O(n)

如果你想对整数进行排序，我在 另一个问题，有很多帮助。您可以使用指数变量来完成此操作，从而避免任何排序。结果是 O(n)：

来自 Alok 的答案< /a> 和 Dan Dyer 的评论 事实证明对一组增量使用指数分布给出了整数序列的均匀分布。

因此，您只需开始生成数字，然后在最后缩放它们。在增量中加 1 可确保您永远不会重复某个值。

import random,sys,math

def genSortedInts(mini,maxi,vals):
    running = 0
    deltas = [random.expovariate(1.0) for i in range(0,vals+1)]
    floats = []
    for d in deltas:
        running += d
        floats.append(running)
    upper = floats.pop()
    valRange = maxi-mini-(vals-1)
    ints = [mini+int(f/upper*valRange)+id for id,f in enumerate(floats)]
    return ints

if __name__ == "__main__":
    vals = 10
    maxi = 80
    mini = 0
    print(genSortedInts(mini,maxi,vals))

请注意 random.expovariate(1.0) 的使用，即 Python指数分布随机数生成器（非常有用！）。在这里，它的调用平均值为 1.0（arg 为 1/mean），但由于脚本针对序列中的最后一个数字进行标准化，因此平均值本身并不重要。

10 个值（最多 80 个）的输出（公平掷骰子）：

[3, 5, 10, 16, 25, 37, 41, 45, 57, 70]

Answer 2

您可以使用通过交换实现的部分Fisher-Yates shuffle。该算法的一个很好的功能是，如果您在 k 交换后停止，则前 k 数字是大小为 k 的随机样本全套。

Answer 3

您可以创建一个包含数字 0 到 8000 的列表。

然后循环 1000 次生成一个介于 0 和列表长度之间的随机数。

从列表中删除该元素并将其添加到输出列表中。

通过删除该元素，您可以确保您的选择是唯一的。

while (outputList.Count < 1000)
{
    index = random.Next(0, inputList.Count);
    outputList.Add(inputList[index]);
    inputList.RemoveAt(index);
}

Answer 4

这是来自 Knuth 的《编程艺术》（来自 Jon Bentley 的《Programming Pearls》），用 Python 实现：

import random

# randomly select m numbers from n candidates    
def random_select(m, n):
    select = m
    result = []
    for i in xrange(n):
        if random.randint(0, n-i) < select:
            result.append(i)
            select -= 1
    return result

random_select(1000, 8000)

这将生成一个按数字顺序排列的随机数列表。它的工作原理是迭代 0-n（即 0-8000）的所有整数，并以（剩余选择数/剩余候选数）的概率随机选择它们。它的运行时间为 O(n)，因此如果 n 与 m 相比非常大，请不要尝试它 - 例如从十亿个数字中选择十个。除了结果列表 (m) 和一些局部变量之外，它不使用任何内存，这与依赖于对长度为 n 的列表进行混洗的解决方案不同。

如果您希望结果按随机顺序排列，请随后对列表进行打乱。

Answer 5

部分 Fisher-Yates，如 @Mark 建议，稍微改动一下，一路存储交换。
这样，它至多会消耗与结果列表 O(m) 一样多的内存。
它也将在 O(m) 中运行 - 而不是 O(n)，就像枚举整个范围的其他解决方案一样 - 因此它在更大的范围上不应该出现问题。
这样，您就可以两全其美。

/// <summary>
/// Generates unique random numbers
/// <remarks>
/// Worst case memory usage is O(min((emax-imin)/2, num))
/// </remarks>
/// </summary>
/// <param name="random">Random source</param>
/// <param name="imin">Inclusive lower bound</param>
/// <param name="emax">Exclusive upper bound</param>
/// <param name="num">Number of integers to generate</param>
/// <returns>Sequence of unique random numbers</returns>
public static IEnumerable<int> UniqueRandoms(
    Random random, int imin, int emax, int num)
{
    int dictsize = num;
    long half = (emax - (long)imin + 1) / 2;
    if (half < dictsize)
        dictsize = (int)half;
    Dictionary<int, int> trans = new Dictionary<int, int>(dictsize);
    for (int i = 0; i < num; i++)
    {
        int current = imin + i;
        int r = random.Next(current, emax);
        int right;
        if (!trans.TryGetValue(r, out right))
        {
            right = r;
        }
        int left;
        if (trans.TryGetValue(current, out left))
        {
            trans.Remove(current);
        }
        else
        {
            left = current;
        }
        if (r > current)
        {
            trans[r] = left;
        }
        yield return right;
    }
}