Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Генерация случайной перестановки


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

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

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

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

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

Автор: Akina 17.10.2007, 16:55
Цитата(CrazyHatter @  17.10.2007,  17:20 Найти цитируемый пост)
Очевидным способом будет 

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


Цитата(CrazyHatter @  17.10.2007,  17:20 Найти цитируемый пост)
генерация случайного числа в диапазоне [0, N-1] и занесение его на следующее место в ответе, а если это число уже присутствует в перестановке

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

Код

for i = 0 to n-1
  r = rand(i, n-1)
  swap x(r), x(i)
next

Автор: esperant0 17.10.2007, 16:57
Цитата(CrazyHatter @ 17.10.2007,  16:20)
 

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

 

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


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

Добавлено через 5 минут и 17 секунд
Цитата(Akina @ 17.10.2007,  16:55)
Цитата(CrazyHatter @  17.10.2007,  17:20 Найти цитируемый пост)
Очевидным способом будет 

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

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

Автор: JackYF 17.10.2007, 18:33
рекомендую посмотреть в исходники stl на метод std::random_shuffle

Автор: esperant0 17.10.2007, 21:38
Цитата(JackYF @ 17.10.2007,  18:33)
рекомендую посмотреть в исходники stl на метод std::random_shuffle

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

Автор: JackYF 17.10.2007, 22:52
Цитата(esperant0 @  17.10.2007,  21:38 Найти цитируемый пост)
зачем исходники?

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

Автор: sergejzr 17.10.2007, 23:32
Цитата(JackYF @  17.10.2007,  17:33 Найти цитируемый пост)
рекомендую посмотреть в исходники stl на метод std::random_shuffle


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

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

Код

for i = 0 to n-1
  r = rand(i, n-1)
  swap x(r), x(i)
next


Цитата

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


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

Цитата

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


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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)