Сгенерировать M уникальных случайных чисел в диапазоне от 1..N. Быстрый алгоритм есть?

Question

[Сергей]

Есть быстрые алгоритмы генерации таких чисел, чтобы они не повторялись ?
Видится сбор чисел от генератора случайных числе в список, и проверка каждого нового на уникальность по списку.
Видится сложность порядка: O(n^2)

Диапазон M < N, и могут быть одинакового порядка, порядок в районе 10000.

Я могу использовать только списки и туплы.

Answer 1

[Николай]

Сгенерить массив 1..N
Сгенерить случайное число 0 < i < N
Извлечь элемент по этому индексу из массива
Повторить с N-1, ...., N-M.

Answer 2

[GavriKos]

1) Создать список размером N, в котором все элементы - false, пусть будет arr
2) Генерировать число, пусть - value
3) Если arr[value] == false - то заносим число в итоговый список и arr[value] = true. Если arr[value] == true - переходим к пункту 2.

Сложность тем выше, чем ближе m к n.
Можно попробовать генерировать блоками. Например, если n == 100, и от 0 до 10 уже сгенероно >50% чисел - то в этом диапазоне не генерим вообще. Но сходу не могу сообразить словесный алгоритм.

Comments

[Александр Пожарский]

Тогда уж hashmap же, а то и вовсе - hashset.

[GavriKos]

Александр Пожарский в вопросе - могу использовать только списки и туплы. А так да - хешсет наше все в таком случае.

[Александр Пожарский]

GavriKos: а я не внимателен, да. :-)

Answer 3

[Rsa97]

Создать массив X[1..N]
Заполнить его X[i] = i
Сделать много (например, N) перестановок случайных элементов X[rand(1..N)] <=> X[rand(1..N)]
Взять M первых элементов

Answer 4

[Андрей]

Шифруйте на одинаковом ключе блочным шифром с размером блока (2^[log2(N)+1]) порядковые числа (0, 1, 2, ...). Если получилось значение большее чем N, отбрасывайте образец. Блочный шифр с одинаковым ключом обеспечит Вам неповторяемость (биективность) создаваемых чисел. (Только не делайте mod N над результатом !!!)

Comments

[Сергей Соколов]

каким алгоритмом предлагаете шифровать?

Answer 5

[Sayonji]

Если вам не важно наличие строгой оценки, а важна скорость на практике, можете воспользоваться таким методом:
1. Объявляете переменную p=M/N и списки L, R
2. Делаете цикл i=1..N и добавляете число i в L с вероятностью p, иначе в R
3. Теперь в L приблизительно M элементов, пусть d=M - |L|
4. Если d>0, перебрасываете d случайных элементов из R в L, иначе наоборот из L в R
Сложность получится O(N + dN), где d в среднем будет около sqrt(M(N^2-M^2)/2) / N

Теоретическая оценка получается O(Nsqrt(M)), что хуже, чем случайное перемешивание списка 1..N за O(NlogN).

Answer 6

[Евгений Кучеренко]

Создаете упорядоченный список/массив натуральных чисел от 1 до N;
Генерируете случайное число от 0 до длины массива - 1;
Забираете из исходного массива элемент с индексом сгенерированного числа и вставляете его в новый массив.
Предполагается, что исходный массив будет обрезан.
Повторяем операцию.

Вроде как раз O(N^2) получается.

Интересно, откуда такая задача?
Я Erlang не знаю, но на JavaScript самое изящное решение выглядит так:

const createArray = (length) => Array.from( {length: length}, (v, k) => k );

const shuffle = (array) => array.sort( (a, b) => Math.random() - 0.5 );

shuffle(createArray(10000));

Теоретическое время работы такого алгоритма -O ( N^2 * Log (N) ), однако как показывают тесты, на практике - O (N)

const test = (n) => {
	let start = new Date().getTime();
	shuffle(createArray(n));
  let finish = new Date().getTime();
  return console.log(`Lead time: ${Math.round(finish - start)} msec`)
}

test(10000)
test(100000)
test(1000000)

Answer 7

[GreatRash]

1) Из меня математик как из палки ружьё.
2) Создать массив чисел от 1 до N.
3) Перетасовать массив.
4) Взять первые М чисел.

Comments

[Сергей]

Ситуация осложняется использованием только списков и туплов.

[GreatRash]

Сергей: Что есть тупл я не знаю, а в списке разве нет индексов?

[Сергей]

Нет, это односвязанный список.

[GreatRash]

Сергей: а как по нему итерироваться? Порядок данных там гарантирован? Вообще, что за язык?

[GreatRash]

Сергей: А, увидел Erlang, ужаснулся синтаксису... нихрена не понятно

[Sayonji]

Сергей: Можно перемешать список при помощи merge sort по случайному предикату. Получите nlogn.

[Rsa97]

Сергей: А кто вам сказал, что в Erlang нет массивов? erlang.org/doc/man/array.html

[Сергей]

Rsa97: это составной тип:
2> array:from_list([1,2,3,4,5]).
{array,5,10,undefined,
{1,2,3,4,5,undefined,undefined,undefined,undefined,
undefined}}

Базовые типы - таплы и листы.

[Rsa97]

Сергей: А какая разница? Реализован он на низком уровне, позволяет извлечь и записать любой элемент.

Answer 8

[Сергей Соколов]

Нужна функция биективной (1:1) проекции упорядоченных чисел от 1 до N на такой же диапазон.

Самый простой пример, чтобы понятно представить идею, это зеркалирование порядка битов в числе:

0 000 -> 000 0
1 001 -> 100 4
2 010 -> 010 2
3 011 -> 110 6
4 100 -> 001 1
5 101 -> 101 5
6 110 -> 011 3
7 111 -> 111 7

Теперь, чтобы получить очередное случайное, просто берите подряд следующее.

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

Так не придётся хранить, перемешивать, генерировать случайные. Для "псевдослучайности" можно варьировать функцию. Например, не зеркалить порядок битов, а перемешивать биты как-то иначе. Каждый вариант перемешки битов создаёт новый «перемешанный массив» всех возможных значений.

Главное, это быстро вычисляется и требует минимальных ресурсов.