一个子集中的五个唯一随机数

一个随机号码呼叫就足够了。

如果要选择范围1-n中5个唯一数字的子集,请选择1到(n选择r)中的随机数字。

保持从1到(n选择r)的1-1映射到可能的5元素子集集,这样就完成了。此映射是标准的,可以在Web上找到,例如: http://msdn.microsoft.com/en-us/library/aa289166%28VS.71%29.aspx

举个例子:

考虑从五个数字中生成两个数字的子集的问题:

_1,…,5的可能2元素子集是

1. {1,2}
2. {1,3}
3. {1,4}
4. {1,5}

5. {2,3}
6. {2,4}
7. {2,5}

8. {3,4}
9. {3,5}

10. {4,5}

现在5选择2等于10。

所以我们选择一个从1到10的随机数。说我们得了8。现在我们按照上面的顺序生成第8个元素:它给出3,4,所以您需要的两个数字是3和4。

我链接到的msdn页面向您展示了一个生成集合的方法,给出了这个数字。即给定8,则返回集合3,4。

您的最佳选择是循环,如:

$max = 20;
$numels = 5;
$vals = array();
while (count($vals) < $numels) {
    $cur = rand(0, $max);
    if (!in_array($cur, $vals))
        $vals[] = $cur;
}

对于小范围,可以使用 array_rand :

$max = 20;
$numels = 5;
$range = range(0, $max);
$vals = array_rand($range, $numels);

您还可以生成一个介于0和max之间的数字,另一个介于0和max-1之间的数字,…介于0和max-4之间。然后将x和为第n个生成的数字,其中x是按这种方式计算的数字:

• 取第n次迭代中生成的数字并将其赋给x
• 如果它大于或等于第一次迭代中生成的,则递增
• 如果这个新数字大于或等于在第二次迭代中生成(并更正)的数字,则递增它。
• …
• 如果这个新数字大于或等于第(n-1)次迭代中生成(并修正)的数字,则递增它。

映射如下:

1 2 3 4 5 6 7 8 9 (take 4)
1 2 3 4 5 6 7 8 9 (gives 4)

1 2 3 4 5 6 7 8 (take 5)
1 2 3 5 6 7 8 9 (gives 6)

1 2 3 4 5 6 7 (take 6)
1 2 3 5 7 8 9 (gives 8)

1 2 3 4 5 6 (take 5)
1 2 3 5 7 9 (gives 7)

example, last extraction:
x = 5
x >= 4? x == 6
x >= 6? x == 7
x >= 8? x == 7

这个问题的一般形式真的很有趣。应该从一个元素池中选择(并将它们从池中删除)还是应该在点击一个已经占用的元素时循环?

据我所知,Random.sample的python库实现 运行时选择 这两种方法之间的比例取决于输入列表的大小和要选择的元素的数目。

源代码中的注释:

    # When the number of selections is small compared to the
    # population, then tracking selections is efficient, requiring
    # only a small set and an occasional reselection.  For
    # a larger number of selections, the pool tracking method is
    # preferred since the list takes less space than the
    # set and it doesn't suffer from frequent reselections.

但是,在OP提到的特定实例中(选择5个数字),我认为循环“同时命中所取的数字”是可以的,除非伪随机生成器被破坏。

既然你只是在寻找不同的想法,这里有一个:

呼喊 Random.org 生成所需的一组随机数。

如果你知道大小n,那么保持每个数字的概率为5/n,生成一个介于0和1之间的随机数,如果它小于5/n,则保持该项。当我们有5件物品时停止。

如果我们不知道使用 resorvoir sampling .

Artefactor上述第二个解决方案在C中的实现,作为ICollection的助手和扩展方法:

static class Program {

    public static IEnumerable<int> Subset(int max) {
        Random random = new Random();
        List<int> selections = new List<int>();
        for (int space = max; space > 0; space--) {
            int selection = random.Next(space);
            int offset = selections.TakeWhile((n, i) => n <= selection + i).Count();
            selections.Insert(offset, selection + offset);
            yield return selection + offset;
        }
    }

    public static IEnumerable<T> Random<T>(this ICollection<T> collection) {
        return Subset(collection.Count).Select(collection.ElementAt);
    }

    static void Main(string[] args) {
        Subset(10000).Take(10).ToList().ForEach(Console.WriteLine);
        "abcdefghijklmnopqrstuvwxyz".ToArray().Random().Take(5).ToList().ForEach(Console.WriteLine);
    }
}