非均匀随机发生器

Question

我需要生成 6 个从 1 到 37 的唯一随机数；起初我使用了一个简单的数组映射：

private int k=6, n=37;

public int[] Results ()
{
    // fill an array with numbers 1 2 3 . . . n
    int[] numbers = new int[n];
    for (int i = 0; i < numbers.length; i++)
        numbers[i] = i + 1;

    // draw k numbers and put them into a second array
    int result[] = new int[k];
    for (int i = 0; i < result.length; i++)
    {
        // make a random index between 0 and n - 1
        int r = (int) (Math.random() * n);
        // pick the element at the random location
        result[i] = numbers[r];
        // move the last element into the random location
        numbers[r] = numbers[n - 1];
        n--;
    }
    return result;
}

问题是在很多情况下我得到了接近均匀的分布（特别是当我进行少于 10 次绘制时），即：1,9,16,18,24,30 或 5 ,16,18,22,26,29

我真正需要的是一个真正的随机发生器，它可以给我这样的结果： 11、16、25、29、30、32 或 4、8、9、15、18、19 少于 10 次抽奖。

我还看到了类似的 HashMap 实现：

import java.util.*;

public class RandomHash
{
    HashMap numbers = new HashMap() ;
    Random rnd_gen = new Random() ;

    RandomHash()
    {
        for(;;)
        {
            int rnd_num = rnd_gen.nextInt() ;
            Integer rnd_num_obj = new Integer(rnd_num) ;

            if (! numbers.containsKey(rnd_num_obj) )
            {
                numbers.put(rnd_num_obj, rnd_num_obj) ;
                /* Do whatever with the number */
                break ;
            } /* else loop and get another rnadom num */

        } /*end for*/
    }
}

问题是我目前不知道如何将随机数发生器和哈希图分别绑定到 6 和 32。哈希图会给出更多混乱的结果吗？

Answer 1

您可以通过一次随机号码调用来完成此操作！ 10 太多了 :-)

请注意，您的 6 个数字正好有 37 种选择 6 种可能性。

因此，您需要做的就是选择 1 到 2324784 之间的随机数（即 37 选 6）。

然后利用映射得到6个元素对应的组合。有关映射的示例，请参阅此处：生成数学组合的第 m 个词典元素。

MSDN 代码的 Java 端口位于：http: //the-lost-beauty.blogspot.com/2010/07/generating-combinations-in.html

Answer 2

你要求随机数，这就是你得到的。您的两个示例：11,16,25,29,30,32 和 4,8,9,15,18,19 的可能性比您认为均匀分布的结果要小。

例如，让我们看一下您的最后结果，为了简化起见，假设您希望所有数字都小于或等于 19。如果您选择 1 到 32 之间的单个数字，则您有 19/32 的机会（约 59%）为 19 或更少。如果您选择 1 到 32 之间的 6 个不同数字，则所有这些数字均为 19 或更少的可能性不到 3%。

当运行代码 100 次时，我实际上得到了 5 个满足要求的列表，这比统计预期多了两个：

[3, 8, 13, 16, 18, 19]

[2, 3, 6, 8, 10, 14]

[2、6、7、8、13、18]

[4、5、9、10、11、12]

[8、12、13、15、16、17]

Answer 3

我只需打乱第一个数组（在初始化步骤之后）并获取前 6 个元素。您可以使用

Collections.shuffle( Arrays.asList(array) );

语言的内置函数来对数组进行洗牌之类的操作。

如果您从 1,000,000 个元素中进行选择，则可能会出现性能问题，但只有 37 个元素时，我认为洗牌是一个更清晰的解决方案。

Answer 4

模 37 的线性同余发生器，具有适当选择的参数？

或者，

List l = Arrays.asList(numbers);
Collections.shuffle(l);
return l.subList(0,k).toArray();

请注意，它期望数字是一个 Object[] 并返回另一个 Object[]。

Answer 5

这是一个非均匀分布：

return new int[]{1,2,3,4,5,6};