在区间[0,8000]中生成1000个不同的整数的算法是什么？

Question

可能重复：
如何高效地生成一个在0到上限N之间的K个不重复整数列表 除了以下两种方法，有什么其他方法可以生成范围在[0,8000]内的1000个不同的随机整数吗？

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

- snap

---

第一种方法为何被称为“naive（天真）”？检查它是否在数组中会使其不再是随机的。如果它是随机的，那么重复项是可以预期的。 - Amy B

重复问题：https://dev59.com/3nVC5IYBdhLWcg3wvT7g https://dev59.com/3nVC5IYBdhLWcg3w4VNy - Nick Dandoulakis

第一个案例中的O(n²)是从哪里得来的？每个数字需要尝试m次，其中m是几何分布。这意味着复杂度更糟。 - Jørgen Fogh

for(i=0;i<1000;i++) print i;（这只是一个玩笑） - user132014

@The Last Ninja：你需要再次检查，直到获得一个新的数字。这意味着你需要对每个新数字运行几何分布数量的列表。我不知道如何简化求解答案的总和，但我认为它是O(n^3)。 - Jørgen Fogh

Answer 1

你可以使用一种利用交换实现的部分Fisher-Yates 洗牌算法。该算法的一个好处是，如果在进行 k 次交换后停止，前 k 个数字将会是完整集合中大小为 k 的随机样本。

- Mark Byers

---

+1. 我本来想建议整个数组洗牌；不知为何，这个显而易见的优化没有出现在我的脑海中。 - Nick Johnson

问题在于你仍然需要从[0,8000]创建一个数组。你能否在没有额外开销的情况下创建一个排列？如果你想要在1..1,000,000之间有10个唯一的数字，该怎么办？ - Ray

从技术上讲，您可以将其制作为使用字典实现的稀疏数组，任何没有设置值的位置都被视为等于其索引。 - Amber

@Dav：好建议。这将节省从[0, 8000]构建整数列表的O(n)时间。 - Mark Byers

我不记得提到过位数组？ - Amber

@Dav：（好主意：对于这个问题和通常的k排列，我正在做类似的事情：https://dev59.com/W3E95IYBdhLWcg3wPrgI#2394308） - Andras Vass

Answer 2

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

然后循环1000次，在列表长度之间生成一个随机数。

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

通过删除元素，确保你的选择是唯一的。

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

- ChrisF

---

这将运行在O(n^2)，因为对于向量或数组的RemoveAt操作是O(n)。 - Dave Kirby

Answer 3

这段代码来自于 Knuth 的《计算机程序设计艺术》（通过 Jon Bentley 的《编程珠玑》），使用 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的列表的解决方案。

如果您希望结果以随机顺序呈现，则可以在列表洗牌后进行。

- Dave Kirby

---

Pythonic 变体：import random; random.sample(xrange(8000), 1000) - Ants Aasma

Answer 4

Partial 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;
    }
}

- Andras Vass

Answer 5

无需排序的有序列表，O(n)

如果你想要整数排序，我在另一个问题中得到了很多帮助，最终找到了这个答案。你可以使用指数变量来实现，从而避免任何排序。结果是O(n)：

根据Alok的回答和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]

- Phil H