Найдите ожидаемые свопы для сортировки заданного массива, где вероятность замены любой инверсионной пары равна

Опубликовано: 21 Сентября, 2022

Для заданного массива arr[] , состоящего из перестановок первых N натуральных чисел, задача состоит в том, чтобы найти ожидаемое количество перестановок для сортировки заданного массива, где вероятность перестановки любой инверсионной пары равна, а вероятность перестановки любой неинверсионной пара 0.

Примеры:

Input: arr[] = {3, 2, 1}
Output: 2.3333
Explanation: The given array can be sorted in non-decreasing order order using sequences of swaps as shown in the image below. 
 

The expected numbers of swaps of each node can be calculated by 1 + (average of expected number of swaps of all the child nodes). 
Since the nodes 3, 9, 10, 11, and 12 are already sorted, the number of expected swaps to sort them are 0.
The expected number of swaps of nodes 5, 6, 7, and 8 will be 1.
Similarly, the expected number of swaps of nodes 2 and 4 will be 2.
Hence, the expected number of swaps of node 1 is 1 + (2 + 2 + 0)/3 = 1 + 1.3333 = 2.3333

Input: arr[] = {1, 3, 2}
Output: 1.0
Explanation: Since there is only 1 inversion pair (arr[1], arr[2]), the expected number of swaps is 1.

Подход: Данная проблема может быть решена с помощью рекурсии и возврата с использованием мемоизации, которая основана на следующих наблюдениях:

  • Инверсия в массиве определяется как два индекса (i, j) , такие что i < j и arr[i] > arr[j] . Ожидаемое количество перестановок может быть рассчитано рекурсивно после замены целых чисел каждой допустимой инверсии по одной за раз и рекурсивного вызова перестановки после перестановки до тех пор, пока вся перестановка не будет отсортирована.
  • Предположим, что в текущей перестановке имеется K инверсий, и после замены i -й инверсии ожидаемое количество перестановок для сортировки перестановки обозначается P i . Следовательно, ожидаемое количество перестановок после перестановки всех возможных инверсий будет равно (P 1 + P 2 + … + P K )/K .

Используя приведенные выше наблюдения, данная проблема может быть решена с помощью следующих шагов:

  • Создайте карту, скажем, памятку , в которой хранится ожидаемое количество свопов для данной перестановки.
  • Создайте рекурсивную функцию expectSwaps() , которая принимает перестановку в качестве аргумента и возвращает ожидаемое количество свопов.
  • В функции expectSwaps() , если ожидаемые свопы текущей перестановки уже рассчитаны, вернуть ответ. В противном случае выполните итерацию по каждой допустимой инверсии и замените индекс текущей инверсии и рекурсивно вызовите перестановку после замены.
  • Найдите сумму ожидаемых свопов после каждого допустимого свопа в переменной, скажем, res , и количество инверсий в переменной, скажем, K.
  • После выполнения вышеуказанных шагов выведите в качестве результата значение res/K .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N 2 N!)
Вспомогательное пространство: O(N!)

РЕКОМЕНДУЕМЫЕ СТАТЬИ