Пять уникальных случайных чисел из подмножества

Ответ 1

Достаточно одного случайного номера.

Если вы хотите выбрать подмножество из 5 уникальных чисел в диапазоне 1-n, выберите случайное число в 1 для (n выберите r).

Сохраняйте отображение 1-1 от 1 до (n выберите r) до набора возможных 5 элементов подмножеств, и все готово. Это сопоставление является стандартным и может быть найдено в Интернете, например здесь: http://msdn.microsoft.com/en-us/library/aa289166%28VS.71%29.aspx

В качестве примера:

Рассмотрим задачу о создании подмножества из двух чисел из пяти чисел:

Возможное 2-элементное подмножество {1,..., 5} -

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. Теперь мы генерируем восьмой элемент в приведенной выше последовательности: который дает {3,4}, поэтому два числа, которые вы хотите, равны 3 и 4.

На странице msdn, с которой я связан, показан метод сгенерирования набора с учетом номера. т.е. с учетом 8, оно возвращает множество {3,4}.

Ответ 2

Ваш лучший вариант - это цикл, например:

$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 до макс, другое от 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

Ответ 3

Общая форма этого вопроса действительно интересна. Следует ли выбрать из пула элементов (и удалить их из пула) или один цикл "при ударе" уже принятого элемента?

Насколько я могу судить, реализация библиотеки python для random.sample выбирает во время выполнения между двумя способами в зависимости от доли размера входного списка и количества элементов для выбора.

Комментарий от исходного кода:

    # 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 чисел), я думаю, что цикл "при ударе принятого числа" в порядке, если только псевдослучайный генератор не сломан.

Ответ 4

Поскольку вы просто ищете разные идеи здесь:

Вызовите Random.org, чтобы создать набор случайных чисел, которые вам нужны.

Ответ 5

Если вы знаете размер N, тогда сохраняйте каждое число с вероятностью 5/N, генерируя случайное число от 0 до 1, и если оно меньше 5/N, сохраните элемент. Остановитесь, когда у нас есть 5 предметов.

Если мы не знаем, что N использует resorvoir sampling.

Ответ 6

Реализация второго решения Artefacto выше в С# в качестве помощника и метода расширения на 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);
    }
}