Здравствуйте всем. У меня возник такой вопрос, может быть кто-нибудь подскажет:

Мне нужно сгенерировать случайную перестановку массива из N чисел [0, 1 ... N-1].

Очевидным способом будет генерация случайного числа в диапазоне [0, N-1] и занесение его на следующее место в ответе, а если это число уже присутствует в перестановке, то генерировать случайное число дальше до тех пор пока не получится ранее не встречавшееся. Т.е. пусть  X  - наша перестановка, тогда последовательно присваиваем X[0]=random(0, N-1), X[1]=random(0, N-1) и так далее. 

Однако такой способ очень накладный, когда приходится иметь дело с перестановкой из, скажем, 1000 элементов. На последней итерации придется полчаса ждать, пока сгенерируется одно единственное недостающее число.

Может быть кто-нибудь знает или встречал более эффективные алгоритмы получения случайной перестановки? Мне бы это очень пригодилось.
Спасибо.

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



вообще-то проще на втором шаге генерить в диапазоне [0, N-2], далее в диапазоне [0, N-3]... и считать соотв. элементы с учетом пропуска уже выбранных ранее.

ДА есть способы.


Но Ваш имеет сложность n lg n . Почему Вы называете это очень накладным?

Добавлено через 5 минут и 17 секунд

Конечно правильным.

рекомендую посмотреть в исходники stl на метод std::random_shuffle

зачем исходники? если просят алгоритм?

из исходников при удачных условиях можно понять алгоритм.

Там как раз алг, который Akina в три строки написал 

2 Akina: Спасибо, вот это наверное как раз то, что я искал:





2 esperant0: просто я пишу метод, который требует последовательного построения достаточно большого числа случайных перестановок. В моем массиве порядка 2000 значений, а если перестановок будет, скажем, несколько десятков тысяч, то использование неэффективного алгоритма заметно увеличит время работы.



2 JackYF: кстати, спасибо, я не знал что такой есть. вполне возможно, что пригодится.