Допустим, мне нужно получить случайную перестановку из N элементов. Алгоритмы
известны. Я взял алгоритм Саттоло. Действует он так.
Расположим элементы в некотором порядке. Возьмем последний элемент и переставим его с любым предыдущим. Затем возьмем предпоследний элемент и переставим его с любым предыдущим. И так далее до начала расположения всех элементов. Получим случайную перестановку. Хорошо.
Пусть теперь мне нужно получить последовательность случайных перестановок по этому алгоритму. Читаю, читаю... никак не соображу, всегда ли нужно брать одну и ту же исходную перестановку или, что экономнее, каждый раз можно брать предыдущую перестановку, предыдущий член последовательности?
Если брать одну и ту же, то почти очевидно, что рано или поздно мы получим любую перестановку, притом с практически одинаковой частотой. А вот если каждый раз брать предыдущую, то это как-то... неочевидно. Вдруг последовательность раньше времени зациклится?!
Иными словами, всегда ли из любой перестановки можно получить любую другую через некоторое число членов последовательности? (Равночастотность мне не очень важна.)
переставляемого элемента в примере выше всегда меньше индекса 
, с которым элемент должен быть переставлен. В результате вместо тасования Фишера — Йетса получим алгоритм Саттоло, который образует перестановки, затрагивающие все элементы. В частности, в этом случае никакой элемент не может оказаться на начальной позиции.