Случайная перестановка с [i]! = I

Question

Обычно случайная перестановка для массива с n элементами означает равномерное распределение из n! возможностей, и для этого используется случайное перемешивание Кнута:

for i from n − 1 downto 1 do
  j ← random integer with 0 ≤ j ≤ i
    exchange a[j] and a[i]

Но с ограничением, a[i] != iЯ понятия не имею, как сформировать такую ​​перестановку равномерно.

Например, при n = 3, как случайным образом сформировать перестановку из представленных ниже возможностей?

{1, 2, 0}, {2, 0, 1}

Answer 1

Перестановка без фиксированных точек называется расстройство

Поскольку число derangemets равно O (n!) , точно так же как количество перестановок, генерация всех перестановок и фильтрация тех, которые не являются отклонениями, не повредят вашей производительности.

Быстрый поиск вернул мне эти слайды , которые описывают другой алгоритм.

Answer 2

Вы не указали, насколько велики ваши массивы или насколько вы обеспокоены эффективностью.Одним из возможных решений было бы просто сделать перемешивание по Кнуту, а затем проверить, удовлетворено ли ваше ограничение, и повторить перемешивание, если нет.

Если вы хотите немного большей эффективности, вы можете попробовать это вместо этого.Поскольку i уменьшается, после шага exchange a[j] and a[i], a[i] фиксируется.Так что просто измените алгоритм на:

for i from n − 1 downto 1 do
  j ← random integer with 0 ≤ j ≤ i; repeat until a[j] != i
    exchange a[j] and a[i]