4

Possible Duplicate:
How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N

What are some alternative methods to generate 1000 distinct random integers in the range [0,8000] as opposed to the following:

  1. naive method: generating a number and checking if it's already in the array. O(n^2)
  2. linear shuffle: generate sequence 0 to 8000, shuffle, take the first 1000. O(n)
4

5 回答 5

12

您可以使用使用交换实现的部分Fisher-Yates 洗牌。这个算法的一个很好的特点是，如果你在k交换后停止，第一个数字是来自完整集合k的随机样本。k

于 2010-04-04T21:56:34.307 回答
2

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

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

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

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

while (outputList.Count < 1000)
{
    index = random.Next(0, inputList.Count);
    outputList.Add(inputList[index]);
    inputList.RemoveAt(index);
}
于 2010-04-04T22:07:04.457 回答
1

这是来自 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 的列表进行混洗的解决方案不同。

如果您希望结果以随机顺序排列，然后将列表随机排列。

于 2010-04-04T22:51:54.380 回答
1

正如@Mark所建议的那样，部分Fisher-Yates会稍微改变一下，沿途存储掉期。
这样，它最多会消耗与结果列表 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;
    }
}
于 2010-04-04T22:53:30.230 回答
0

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

如果您想要对整数进行排序，我在另一个问题中得到了很多帮助。您可以使用指数变量来做到这一点，从而避免任何排序。结果是 O(n)：

根据Alok 的回答和Dan Dyer 的评论，事实证明，对一组增量使用指数分布可以按顺序均匀分布整数。

因此，您只需开始生成数字，然后在最后对其进行缩放。将 1 添加到 delta 可确保您永远不会重复值。

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]
于 2010-04-07T14:13:30.623 回答