Эффективно: случайные числа в фиксированном диапазоне без повторений - PullRequest
Новая
       12

Эффективно: случайные числа в фиксированном диапазоне без повторений

1 голос
/ 27 марта 2011

Эй, ребята, я знаю, что есть миллион вопросов по случайным числам, но именно из-за этого я много искал, но не мог найти что-то похожее на мое - не подразумевая, что его там нет.В любом случае, простите меня, если я повторяю вопрос, просто укажите мне на него, если это так.

Итак, я хочу сделать что-то простое наиболее эффективным способом.

Я хочугенерировать случайным образом все N целых чисел в диапазоне [0, N], один за другим, чтобы не было повторений.

Я знаю, я могу сделать это, вставив все в list, перемешать, получите голову и затем удалите голову из списка.Но тогда я перетасую свой список длины N, N-1 раз.

Любая идея лучше / быстрее?

Ответы [ 2 ]

6 голосов
/ 27 марта 2011

Вы можете просто сделать один случайный случай, а затем пройтись по списку.

Я бы порекомендовал случайный переход Фишера-Йейтса .

0 голосов
/ 17 декабря 2015

Этот вопрос задавался несколько раз, и в каждом случае правильный ответ - перетасовать массив (либо оригинал, либо массив индексов), однако это не является удовлетворительным ответом в случаях, когда числовозможных индексов непомерно велико (либо огромно, либо недостаточно памяти, либо вы просто жаждете максимальной эффективности по любой причине).

Поэтому я хочу добавить альтернативу для полноты картины.Теперь это не совсем случайно, поэтому, если это то, что вам нужно, то не используйте это , однако, если ваша цель просто «достаточно хороша» с минимальными требованиями к памяти, тогда следующий псевдокод может бытьИнтересно: 

function init:
    start = random [0, length)      // Pick a fully random starting index
    stride = random [1, length - 1) // Pick a random step size
    next_index = start

function advance_next_index:
    next_index = (next_index + stride) % length
    if next_index is equal to start then
        start = (start + 1) % length
        next_index = start

Вот пример того, как реализовать функцию многократного использования для захвата псевдослучайных значений: 

counter = length
function pseudo_random:
    counter = counter + 1
    if counter is equal to length then
        init()
        counter = 0
    advance_next_index()
    return next_index

Очень просто pseudo_random вызовет initодин раз каждые length итераций, таким образом, перетасовывая "случайный" шаблон результатов, полученных с помощью advance_next_index, и убедитесь, что для каждых length значений не существует ни одного дубликата.

Повторно;это не совсем случайный алгоритм, поэтому не следует использовать в ситуациях, когда требуется истинная случайность.Тем не менее, результаты являются достаточно случайными для некоторых основных, некритических задач, и он имеет небольшой объем памяти.Например, если вы просто хотите рандомизировать какое-либо поведение в игре, чтобы избежать повторения чего-либо, или если набор данных велик и никогда не подвергается воздействию пользователя (в этом случае он фактически является случайным для него), это займет много временисобрать воедино порядок и каким-то образом использовать его.

Если кто-нибудь знает какие-либо более эффективные алгоритмы с похожими свойствами, пожалуйста, поделитесь!

...