1584. Произвольное тасование

Дана перестановка чисел A длины n.

Рассмотрим следующую процедуру случайного перемешивания изначального массива {1, 2, …, n}.

Для i = 1, 2, …, n последовательно выполняется операция:

· равновероятно выбирается индекс r от 1 до n;

· элементы на позициях i и r меняются местами.

Все выборы r независимы друг от друга. Таким образом, существует ровно nⁿ равновозможных последовательностей случайных выборов.

Определите вероятность того, что после выполнения всех операций получится массив A.

Вход. Каждая строка является отдельным тестом. В ней задано число n (1 ≤ n ≤ 10), а затем элементы массива А – перестановка чисел от 1 до n.

Выход. Для каждого теста выведите в отдельной строке искомую вероятность. Ответ должен содержать не менее 6 десятичных знаков.

Пример входа	Пример выхода
1 1 2 1 2 5 4 2 5 1 3	1.00000000 0.50000000 0.00672000

РЕШЕНИЕ

вероятность

Анализ алгоритма

Изначально у нас есть массив {1, 2, …, n}. Далее выполняется процедура тасования. Нам дана финальная перестановка A. Нужно найти вероятность того, что именно её мы получим после выполнения процедуры.

Искомая вероятность равна:

На каждом шаге тасования выбирается одно число r. Количество вариантов выбора числа r равно n. Количество шагов тасования тоже n. Значит существует nⁿ последовательностей выборов. Отметим, что разные последовательности выборов могут привести к одинаковой итоговой перестановке. Потому что nⁿ намного больше, чем n!.

Занесем в массив cur последовательность {1, 2, …, n}. Будем перебирать все возможные варианты выбора (r₁, r₂, …, r_n), моделируя в cur все возможные процессы тасования (1 ≤ r_i ≤ n). Заметим, что фиксированная последовательность чисел r₁, r₂, …, r_n однозначно определяет, какие именно обмены будут выполнены на каждом шаге, а значит и итоговый массив после завершения процедуры. Если после применения всех обменов мы получили массив A, считаем попытку успешной. Пусть таких попыток получилось s. Тогда искомая вероятность равна

s / nⁿ

Реализуем функцию shuffle, которая осуществляет рекурсивный перебор всех возможных продолжений процесса тасования и подсчитывает, сколько из них приводят к целевой перестановке А.

Функция имеет один параметр pos – номер текущей итерации (стартует с 0). Это означает, что первые pos обменов уже выполнены, а массив cur хранит состояние, полученное после этих операций.

Чтобы уложиться в ограничение по времени, применим следующее отсечение. Пусть выполняется итерация с номером pos, и текущий массив cur отличается от целевого массива A в diff позициях. Осталось выполнить n – pos обменов.

Заметим, что за один обмен можно поставить на свои места не более двух элементов. Следовательно, суммарно за оставшиеся шаги можно исправить максимум 2 * (n – pos) позиций.

Если же diff > 2 * (n – pos), то получить из cur массив A уже невозможно. В этом случае дальнейший перебор не имеет смысла, и текущую ветку рекурсии можно немедленно прервать.

Реализация алгоритма

Объявим рабочие массивы:

· a – заданная перестановка А;

· cur – текущая перестановка при переборе;

int a[10], cur[10];

Функция shuffle рекурсивно перебирает все возможные продолжения процесса тасования, считая, сколько из них приведут к целевой перестановке A.

void shuffle(int pos)

{

Выполнены все n операций. Остаётся проверить – совпадает ли полученный массив cur с требуемым A. Если совпадает, значит найден еще один успешный сценарий. В этом случае увеличиваем countGood.

if (pos == n)

{

for (int i = 0; i < n; i++)

if (cur[i] != a[i]) return;

countGood++;

return;

}

В переменной diff подсчитываем, в скольких позициях текущий массив cur отличается от нужного A.

int diff = 0;

for (int i = 0; i < n; i++)

if (cur[i] != a[i]) diff++;

На данный момент нам осталось выполнить n – pos шагов. За один обмен можно исправить максимум две неправильные позиции. Если уже на данный момент различий больше, то выполнять дальше рекурсию бессмысленно.

Мы просто прекращаем рассматривать эту ветку перебора.

if (diff > 2 * (n - pos)) return;

Перебираем все возможные значения r.

for (int r = 0; r < n; r++)

{

swap(cur[pos], cur[r]);

shuffle(pos + 1);

swap(cur[pos], cur[r]);

}

}

Основная часть программы. Читаем число n – размер массива А.

while (scanf("%d", &n) == 1)

{

Читаем входной массив А. Моделирование всегда начинается с массива {1, 2, …, n}. Его и заносим в cur.

for (int i = 0; i < n; i++)

{

scanf("%d", &a[i]);

cur[i] = i + 1;

}

Запускаем перебор. В переменной countGood подсчитываем, сколько последовательностей случайных выборов приведут к массиву A.

countGood = 0;

shuffle(0);

Вычисляем и выводим ответ.

res = countGood / pow(n, n);

printf("%.6lf\n", res);

}