Генерация случайной перестановки

[alexey007]

Я использую следующий алгоритм для генерации случайной перестановки чисел от$1$ до $n$. В начале разыгрываю случайным образом первое место в перестановке: между всеми числами от $1$ до $n$. Потом разыгрываю второе место в перестановке между числами, за исключением числа, которое выпало в первом розыгрыше. И так далее пока не останется одно число которое занимает последнее место в перестановке. Возникает вопрос, будет ли перестановка случайной и можно ли это как то доказать?

[PAV]

alexey007 в сообщении #581946 писал(а):

Возникает вопрос, будет ли перестановка случайной и можно ли это как то доказать?

Да, будет. Можно.

[Egor1984]

Да, она будет случайной. Случайной можно считать даже перестановку (1, 2, 3), в которой все числа всегда идут по порядку.
Вопрос, конечно, в том, какова вероятность появления будет той или иной перестановки. Будут ли все перестановки при таком способе размещения чисел равновероятны? Ответ положителен. Это классическая задача про вытягивание группой студентов билетов на экзамене.
"В группе n студентов, на экзамене m билетов. Один билет - халявный. Доказать, что вероятность вытащить халявный билет не зависит от того, каким по счету стоит студент".
Доказывается через аппарат условных вероятностей.
Сначала нужно доказать, что если я в произвольной перестановке элементов поменяю два соседних элемента, то получу новую перестановку, у которой вероятность появления будет прежней.
А потом замечательные слова: что так можно получить любую перестановку, следовательно, все перестановки равновероятны.

Философский вопрос: а у вас датчик случайных чисел равномерный? Вернее, он должен быть k-равномерным или k-н-равномерным, в зависимости от способа использования последовательности случайных чисел.

[alexey007]

Спасибо, всем за ответы, особенно Egor1984, очень успокоился. Генератор использую C++ функцию rand() %k, функция генерирует случайные числа по равномерному закону.

[gris]

Я тоже недавно переставлял массив прямо на месте

for (  i=0, i<n-2, i++  ) {   swap(  m[i], m[i+random(n-1-i)];  };

Примерно то же самое: уже заданный массив проходил от первой до предпоследней позиции, переставляя очередной элемент со случайным из элементов с не меньшими номерами.

[Egor1984]

К сожалению, линейный конгруэнтный генератор rand() из стандартной библиотеки C очень плох. Это проверялось много раз на практике и доказано теоретически.
Он не проходит почти все тесты библиотеки diehard!!! Я уж не говорю о тесте на заполнение гиперкуба. Да и период у него маленький, на современных машинах этот период превысить очень просто.
Его лучше не использовать. Особенно в задачах криптографии. Это известный факт.

Мой выбор: Mersenne Twister, или любой из серии генераторов Фибоначи.

Про использование генераторов для метода Монте-Карло смотреть тут http://mathstyle.org/?page=rngresults&language=ru