Матч 47, Произвольное тасование (RandomShuffle)

Произвольное тасование чисел массива А производится согласно следующего алгоритма:

n = длина массива А

for i=1 to n

сгенерировать произвольное число r между 1 и n включительно

поменять местами A[i] и A[r]

Вычислить вероятность того, что массив чисел outputArray получен в результате выполнения операции произвольного тасования набора {1, 2, …, n}. Здесь n равно количеству элементов массива outputArray.

Класс: RandomShuffle

Метод: double probability(vector<int> outputArray)

Ограничения: outputArray содержит перестановку чисел от 1 до n, где n равно количеству элементов массива outputArray, n £ 10.

Вход. Массив outputArray, содержащий перестановку чисел от 1 до n.

Выход. Вероятность того, что массив чисел outputArray получен в результате выполнения операции произвольного тасования набора чисел {1, 2, …, n}.

Пример входа

outputArray

{1}

{1,2}

{4,2,5,1,3}

Пример выхода

1.0

0.5

0.006720000000000001

РЕШЕНИЕ

рекурсия + перебор + вероятность

Занесем в массив cur последовательность {1, 2, …, n}. Будем моделировать все возможные процессы тасования, выбирая в качестве значения r все значения от 1 до n. Процесс тасования состоит из n итераций, на каждой из которых в качестве r можно выбрать любое из n чисел (от 1 до n). Таким образом, из последовательности {1, 2, …, n} в результате тасования можно получить nⁿ других последовательностей, некоторые из которых возможно будут одинаковыми (nⁿ > n!). В переменной s подсчитаем, сколько раз в процессе моделирования из {1, 2, …, n} получится последовательность, заданная в массиве outputArray. Разделив найденное число s на nⁿ, получим искомую вероятность.

Функция shuffle имеет единственный параметр pos – номер проводимой итерации. Для прохождения по времени следует совершить следующее отсечение. Пусть производится pos итерация, а текущий массив cur отличается от исходного m в c позициях. Тогда если c > 2*(n –pos), то очевидно, что за оставшиеся n – pos обменов невозможно из cur получить m. Это следует из того, что за каждый из оставшихся обменов мы можем переставлять максимум 2 элемента.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <cmath>

using namespace std;

int m[10], cur[10];

int n, s = 0;

void shuffle(int pos)

{

int i, c;

if (pos == n)

{

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

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

s++;

return;

}

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

if (m[i] != cur[i]) c++;

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

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

{

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

shuffle(pos + 1);

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

}

}

class RandomShuffle

{

public:

double probability(vector<int> outputArray)

{

n = outputArray.size();

for(int i = 0; i < n; i++) m[i] = outputArray[i],cur[i] = i + 1;

shuffle(0);

return 1.0 * s / pow((double)n,(double)n);

}

};