Упорядочить ряд чисел методом случайного выбора пары чисел

[goza]

Есть ряд натуральных чисел от 1 до 10, записанный в произвольном порядке (например 1, 2, 6, 5, 10, 3, 8, 9, 7, 4). Мы выбираем два случайных места в этом ряду и смотрим: если число в правом месте меньше чем в левом, то меняем эти числа местами, если нет, ничего не делаем. Вопрос: как найти среднее число таких операций случайного выбора для упорядочивания заданного ряда в порядке возрастания? На вход должны подаваться от 1 до 40 таких рядов. Время а на выходе среднее число шагов для каждого поданного ряда, необходимых для упорядочивания. Время выполнения программы не должно превышать 3 секунд.

Моё текущее решение данной задачи на примере более простом следующее: пусть есть такой ряд: [1, 2, 4, 3] (пример 1), тогда есть 6 возможных вариантов выпадения пар чисел, из них подходит только один, поэтому в среднем необходимо 6 операций:
[1, 2, 4, 3] -> (6) -> [1, 2, 3, 4]

Пусть теперь есть такой ряд: [1, 3, 4, 2], здесь опять имеем 6 возможных вариантов выпадения пар чисел, из них существует два варианта, при выпадении которых мы меняем числа местами, значит, чтобы сделать это нужно в среднем 3 шага (отношение общего числа шагов к числу, нас интересующему):
[1, 3, 4, 2] -> (3) -> ([1, 2, 3, 4] , [1, 3, 2, 4])
Здесь две получившиеся последовательности упорядочиваются в среднем за 6 шагов (пример 1), поэтому среднее число упорядочить исходную последовательность есть сумма с весовыми коэффициентами всех возможных продвижений и равно 9.

Такой подход хоть и работает но очень медленный, так как предполагает обход всех вариантов, а это составляет около 10! Есть ли какие-либо идеи, как можно посчитать иначе и быстрее?

[gris]

я бы смоделировал и посмотрел. если теоретически, то попробуйте для двух, трёх чисел.

[goza]

я моделировал, получается ряд чисел от 45 до 140 примерно. при более короткой последовательности (от 1 до 4) получается следующий ряд: 6; 8; 9; 9,6; 10,5; 11; 11,2.

[Lia]

goza
Задача не для олимпиадного раздела. Попробуйте привести более содержательные попытки решения.

[Lia]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:


- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Computer Science»