Неравномерный рандомизатор

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 - это слишком много: -)

Обратите внимание, что есть ровно 37 вариантов выбора 6 для ваших 6 номеров.

Итак, все, что вам нужно сделать, это выбрать случайное число от 1 до 2324784 (то есть 37 выбрать 6).

Затем использовать сопоставление, чтобы получить комбинацию из 6 элементов, отвечающую за ядро.Пример отображения см. Здесь: Генерация m-го лексикографического элемента математической комбинации .

Java-порт кода MSDN находится здесь: 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 или меньше.Если вы выберете 6 различных чисел от 1 до 32, вероятность того, что все они будут равны 19 или меньше, составляет менее 3%.

При 100-кратном выполнении вашего кода я получил пять списков, удовлетворяющих требованию,что на два больше статистически ожидаемого:

[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

Вот неравномерное распределение:

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

Answer 5

Линейный конгруэнтный генератор по модулю 37, с правильно выбранными параметрами?

С другой стороны,

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

Обратите внимание, что он ожидает, что числа будут объектом [], и возвращает другой объект [].