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

Question

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

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

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

Обратите внимание на это любопытство, а не на критическую проблему. Я был бы признателен, если бы все не опубликовали «почему у вас такая проблема?» ответы. Я просто ищу идеи.
Большое спасибо!

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. Say мы получили 8. Теперь мы формируем 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 до макс, другой между 0 и max-1, ... между 0 и max-4. Тогда вы бы подвести х к п-й сгенерированного числа, где х число рассчитывается таким образом:

• Возьмите число, сгенерированное в п-й итерации и присвоить его х
• , если она больше или равно, что генерируется в первой итерации, увеличивать его
• , если это новое число больше или равно, что генерируется (и исправлены) во второй итерации, увеличивать его
• ...
• , если этот новый номер больше или равно тому, что сгенерировано (и исправлено) в (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

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

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

Answer 4

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

Насколько я могу судить, реализация библиотеки 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 5

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

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

Answer 6

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