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

Одного случайного звонка достаточно.

Если вы хотите выбрать подмножество из 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}.

Ваш лучший вариант – это цикл, как в:

 $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 (взять 4)
 1 2 3 4 5 6 7 8 9 (дает 4)

 1 2 3 4 5 6 7 8 (возьмите 5)
 1 2 3 5 6 7 8 9 (дает 6)

 1 2 3 4 5 6 7 (возьмите 6)
 1 2 3 5 7 8 9 (дает 8)

 1 2 3 4 5 6 (возьмите 5)
 1 2 3 5 7 9 (дает 7)

 пример, последняя добыча:
 x = 5
 x> = 4?  x == 6
 x> = 6?  x == 7
 x> = 8?  x == 7

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

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

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

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

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

Если мы не знаем, что N использует резорвуарную выборку .

Реализация второго решения Artefacto выше в 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); } }