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

Question

Я знаю, что подобные вопросы часто возникают, и, вероятно, нет однозначного ответа, но я хочу сгенерировать пять уникальных случайных чисел из подмножества чисел, которое потенциально бесконечно (возможно, 0-20 или 0-1 000 000).
Единственная загвоздка в том, что я не хочу запускать циклы while или заполнять массив.

Мой текущий метод состоит в том, чтобы просто генерировать пять случайных чисел из подмножества минус последние пять чисел.Если какие-либо числа совпадают друг с другом, то они идут на свое место в конце подмножества.Таким образом, если четвертое число совпадает с любым другим числом, оно будет установлено на 4-е число от последнего числа.

Есть ли у кого-нибудь метод, который является «достаточно случайным» и не включает дорогостоящие циклы или массивы?

Пожалуйста, имейте в виду, что это любопытство, а не какая-то критическая проблема.Я был бы признателен, если бы все не опубликовали "почему у вас возникла эта проблема?"ответы.Я просто ищу идеи.
Большое спасибо!

Answer 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}.

Answer 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и 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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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