Как можно перемешать случайным образом элементы некоторого ряда (массива)?

Идеально так:

Берешь первый элемент и меняешь его с любым случайно выбранным элементом от первого до последнего

берешь 2-йй элемент и меняешь его с любым случайно выбранным элементом от 2-го до последнего.

и так до конца.


Все.


Вот неправильно решение:
Берешь первый элемент и меняешь его с любым случайно выбранным элементом от 1-го до последнего

берешь 2-йй элемент и меняешь его с любым случайно выбранным элементом от 1-го до последнего.

и так до конца.


удачи друг

ну, если имеется в виду, чтобы любая комбинация имела одинаковую вероятность, то можно такой алгоритм:
1. на первое место ставим элемент со случайным номером от 1 до N
2. (для удобства) перенумеровываем все остальные элементы от 1 до N-1 (чтобы не было дырки, которая останется от предыдущего элемента)
3. на второе место ставим элемент со случайным номером от1 до N-1
...

ну или тот же алгоритм только с другой стороны:
1. первый элемент ставим на случайное место (от 1 до N)
2. второй на случайное место из оставшихся незанятых (от 1 до N-1)
...

первый алгоритм имеет квадратичную сложность


второй алгоритм надо уточнить.

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


а с заменами, действительно быстрее получается

Решил реализовать "неправильное решение", но переделать в "правильное" при помощи сложения и вычитания труда не составит. А переименовывать элементы, думаю, что будет сложновато.

Результат работы:
D:\Глагол\Приложения\Свои>Мешалка
1, 2, 3
2, 3, 1
D:\Глагол\Приложения\Свои>Мешалка
1, 2, 3
2, 1, 3
D:\Глагол\Приложения\Свои>Мешалка
1, 2, 3
1, 3, 2

Я не уверен, что вы правильно понимаете почему неправильно, неправильное решение.

Ну так объясните, в чём, по-вашему, заключается его "неправильность"...

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

Хы-хы...
оказалось, вполне достаточно покрутить массив из трех элементов, чтобы увидеть доказательство неправильности "неправильного алгоритма"

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

хотя лично для меня это не объясняет так сказать физику процесса - почему и на каком этапе вероятности получаются разными

Интуиция мне тоже не ясна. Но ваше доказательство достаточно.

maxim1000


А вы не обратили внимание на то, что таким рассуждением легко опровергается также и "правильный" алгоритм? ($n (n+1) /2$ операций)

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

В таком случае для "неправильного" алгоритма на выходе получаются те же n! вариантов.

То, что некоторые варианты могут
быть реализованы различными способами еще ничего не говорит о
неправильности алгоритма. Связь между вероятностями выбора очередного элемента для обмена на конкретном шаге алгоритма и вероятностью появления той или иной перестановки из n элементов по завершению работы алгоритма неочевидна.

1. вероятность каждой конкретной последовательности обменов равна 1/n^n
2. вероятность каждой конечной перестановки равна сумме вероятностей тех последовательностей обменов, которые к ней приводят
3. эта вероятность равна (должна быть равна) 1/n!
4. т.к. вероятности всех последовательностей обменов одинаковая, то 1/n!=k*1/n^n, где k - количество разных последовательностей обменов, приводящих к данной перестановке (целое)...