Довільне тасування#1584

Довільне тасування (Розбір)

Спочатку у нас є масив ${1, 2, ..., n}$ \{1, 2, ..., n\}. Далі виконується процедура тасування. Нам дана фінальна перестановка $A$ . Потрібно знайти ймовірність того, що саме її ми отримаємо після виконання процедури.

Шукана ймовірність дорівнює:

\frac{кількість способів отримати А}{загальна кількість способів тасування}

\frac{кількість~способів~отримати~А}{загальна~кількість~способів~тасування}

На кожному кроці тасування вибирається одне число $r$ . Кількість варіантів вибору числа $r$ дорівнює $n$ . Кількість кроків тасування теж $n$ . Отже існує $n^{n}$ n^n послідовностей виборів. Відзначимо, що різні послідовності виборів можуть призвести до однакової підсумкової перестановки. Тому що $n^{n}$ n^n набагато більше, ніж $n!$ .

Занесемо в масив $c u r$ послідовність ${1, 2, ..., n}$ \{1, 2, ..., n\}. Будемо перебирати всі можливі варіанти вибору $(r_{1}, r_{2}, ..., r_{n})$ (r_1, r_2, ..., r_n), моделюючи в $c u r$ всі можливі процеси тасування $(1 \leq r_{i} \leq n)$ (1 \le r_i \le n). Зауважимо, що фіксована послідовність чисел $r_{1}, r_{2}, ..., r_{n}$ r_1, r_2, ..., r_n однозначно визначає, які саме обміни будуть виконані на кожному кроці, а отже і підсумковий масив після завершення процедури. Якщо після застосування всіх обмінів ми отримали масив $A$ , вважаємо спробу успішною. Нехай таких спроб вийшло $s$ . Тоді шукана ймовірність дорівнює

s / n^{n}

s / n^n

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

Функція має один параметр $p os$ — номер поточної ітерації (стартує з $0$ ). Це означає, що перші $p os$ обмінів уже виконані, а масив $c u r$ зберігає стан, отриманий після цих операцій.

Щоб вкластися в обмеження за часом, застосуємо наступне відсічення. Нехай виконується ітерація з номером $p os$ , і поточний масив $c u r$ відрізняється від цільового масиву $A$ у $d i f f$ позиціях. Залишилося виконати $n - p os$ n - pos обмінів. Зауважимо, що за один обмін можна поставити на свої місця не більше двох елементів. Отже, сумарно за решту кроків можна виправити максимум $2 \cdot (n - p os)$ 2 \cdot (n - pos) позицій.

Якщо ж $d i f f > 2 \cdot (n - p os)$ diff > 2 \cdot (n - pos), то отримати з $c u r$ масив $A$ вже неможливо. У цьому випадку подальший перебір не має сенсу, і поточну гілку рекурсії можна негайно перервати.

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

Оголосимо робочі масиви:

$a$ — задана перестановка $А$ ;
$c u r$ — поточна перестановка при переборі;

int a[10], cur[10];

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

void shuffle(int pos) 
{

Виконані всі $n$ операцій. Залишається перевірити — чи збігається отриманий масив $c u r$ із необхідним $A$ . Якщо збігається, значить знайдено ще один успішний сценарій. У цьому випадку збільшуємо $co u n tG oo d$ .

  if (pos == n) 
  {
    for (int i = 0; i < n; i++)
      if (cur[i] != a[i]) return;
    countGood++;
    return;
  }

C++

У змінній $d i f f$ підраховуємо, у скількох позиціях поточний масив $c u r$ відрізняється від потрібного $A$ .

  int diff = 0;
  for (int i = 0; i < n; i++)
    if (cur[i] != a[i]) diff++;

На даний момент нам залишилося виконати $n - p os$ 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]);
  }
}

C++

Основна частина програми. Читаємо число $n$ — розмір масиву $А$ .

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

Читаємо вхідний масив $А$ . Моделювання завжди починається з масиву ${1, 2, ..., n}$ \{1, 2, ..., n\}. Його і заносимо в $c u r$ .

  for (int i = 0; i < n; i++)
  {
    scanf("%d", &a[i]);
    cur[i] = i + 1;
  }

Запускаємо перебір. У змінній $co u n tG oo d$ підраховуємо, скільки послідовностей випадкових виборів призведуть до масиву $A$ .

  countGood = 0;
  shuffle(0);

Обчислюємо і виводимо відповідь.

  res = countGood / pow(n, n);
  printf("%.6lf\n", res);
}