Взбалтывание контейнера пока его элементы не упорядочатся

@SomniPhobia · Регистрация: 22.11.2017

Author24 — интернет-сервис помощи студентам

Всем привет!
Я к Вам пришёл из раздела C++.
Я написал следующий код на C++

Кликните здесь для просмотра всего текста

C++

#include <iostream> 
#include <random>
#include <algorithm>
#include <numeric>
 
int main()
{
    std::random_device rd;
    const size_t len = 10u;
 
    std::vector<int> box(len);
    std::iota(std::begin(box), std::end(box), 1);
    std::shuffle(std::begin(box), std::end(box), rd);
    unsigned long long count = 0u;
    for (;;++count)
    {
        if (!is_sorted(std::begin(box), std::end(box)))
            std::shuffle(std::begin(box), std::end(box), rd);
        else
            break;
    }
    for (auto value : box)
    {
        std::cout << value << " ";
    }
    std::cout << "\n" << count << "\n";
 
    return 0;
}

Я не знаю, знаете ли Вы данный язык программирования, поэтому дам Вам пояснения по коду.
Суть его заключается в том, что значением переменной len задаём длину последовательности, формируемой в контейнере box. После строки std::vector<int> box(len); в контейнере box имеем len штук элементов, каждый из которых является нулём. Функция std::iota() перезаписывает все эти len нулей числами от 1 (третий аргумент функции) до конца контейнера (до числа len) с шагом 1.
Например, при len = 5; после строки 12 и до строки 13 контейнер box имеет наполнение 1 2 3 4 5.
В строке 13 функция std::shuffle() случайным образом перемешивает содержимое контейнера box (событие "последовательность элементов в контейнере не изменилась после перемешивания" имеет равновероятное событие быть. То есть случайно может после перемешивания оказаться так как было до перемешивания). То есть, функция std::shuffle() взбалтывает контейнер, однако случайно его содержимое может остаться прежним 1 2 3 4 5.
В строке 17 функция std::is_sorted() возвращает true, если в контейнере box все элементы упорядочены по неубыванию и false в противном случае.
! означает отрицание.
Если последовательность не упорядочена (проверка в строке 17) снова взбалтываем контейнер (строка 18), иначе выходим из "бесконечного" цикла (break; в строке 20).
По завершении цикла, контейнер box будет иметь упорядоченное содержание, ведь из цикла в строках 15 - 21 можно выйти только если содержимое контейнера упорядочено по неубыванию иначе в цикле будет снова и снова происходить перемешивание элементов контейнера.
По завершении цикла, переменная count имеет значение численно равное количеству итераций цикла. count имеет следующий смысл -> сколько раз понадобилось хаотично перемешать содержимое контейнера, чтобы в нём все элементы случайно стали упорядочены по неубыванию.
Циклом в строках 22 - 25 выводим на консоль содержимое контейнера box, чтобы убедиться в том, что элементы упорядочены по неубыванию.
В строке 26 выводим на консоль значение count.

Взбалтывание контейнера пока его элементы не упорядочатся

Вопрос:
С использованием математического аппарата, помогите рассчитать математическое ожидание получения неубывающей последовательности (усреднённое количество взбалтывания контейнера) для каждого из len (количество элементов в последовательности box, например, при len от 1 до 15 с шагом 1), чтобы построить график математического ожидания от len (если желаете, можете его построить. Мне интересно каким будет закон этот).
Другими словами: Для каждого из значений len найти среднее количество взбалтываний последовательности, приводящее к её случайному упорядочиванию, при количестве измерений (запусков программы при одном и том же len) стремящемуся к бесконечности.
Приведите ход расчёта, чтобы можно было подставить любое значение для len и получить для этой точки значение математического ожидания.
Всем спасибо!

@jogano · 17.08.2019, 18:35

Можно и математически.
Так как для len элементов существует len! перестановок, и при взбалтывании появление каждой перестановки равновероятно, включая исходную, то вероятность появления определённой перестановки при одном взбалтывании (например, упорядоченный набор чисел по возрастанию) равна 1/len!, а вероятность получить что-то другое 1-1/len!. Это была комбинаторика. Теперь теория вероятностей.
Имеем независимые испытания Бернулли с вероятностью "успеха" (получения нужной перестановки в одном взбалтывании) p=1/len!, и вероятностью неудачи q=1-p. Интересует матожидание случайной величины Х количества опытов до получения нужной перестановки, включая эту последнюю удачную операцию. Эта величина имеет геометрическое распределение, то есть $https://www.cyberforum.ru/cgi-bin/latex.cgi?P\left(X=k \right)=pq^{k-1}, \: k\geq 1$ . Можно посмотреть в Википедии, в статье "Геометрическое распределение", чему равно матожидание МХ (правый столбец) - оно равно 1/p, то есть len!. А можно и вывести самому, для этого вычислить сумму $https://www.cyberforum.ru/cgi-bin/latex.cgi?MX=\sum_{k=1}^{+\infty}kpq^{k-1}=...=\frac{1}{p}$ .
То есть ваша функция среднего количества взбалтываний f(len)=len!

@SomniPhobia · 17.08.2019, 20:36 **[ТС]**

jogano, отличное и развёрнутое объяснение. Спасибо!

@jogano $Эксперт по математике/физике$ 6358 / 4065 / 1512 Регистрация: 09.10.2009 Сообщений: 7,550 Записей в блоге: 4
	17.08.2019, 18:35	2
	Сообщение было отмечено SomniPhobia как решение Решение Можно и математически. Так как для len элементов существует len! перестановок, и при взбалтывании появление каждой перестановки равновероятно, включая исходную, то вероятность появления определённой перестановки при одном взбалтывании (например, упорядоченный набор чисел по возрастанию) равна 1/len!, а вероятность получить что-то другое 1-1/len!. Это была комбинаторика. Теперь теория вероятностей. Имеем независимые испытания Бернулли с вероятностью "успеха" (получения нужной перестановки в одном взбалтывании) p=1/len!, и вероятностью неудачи q=1-p. Интересует матожидание случайной величины Х количества опытов до получения нужной перестановки, включая эту последнюю удачную операцию. Эта величина имеет геометрическое распределение, то есть $https://www.cyberforum.ru/cgi-bin/latex.cgi?P\left(X=k \right)=pq^{k-1}, \: k\geq 1$ . Можно посмотреть в Википедии, в статье "Геометрическое распределение", чему равно матожидание МХ (правый столбец) - оно равно 1/p, то есть len!. А можно и вывести самому, для этого вычислить сумму $https://www.cyberforum.ru/cgi-bin/latex.cgi?MX=\sum_{k=1}^{+\infty}kpq^{k-1}=...=\frac{1}{p}$ . То есть ваша функция среднего количества взбалтываний f(len)=len! 2

@SomniPhobia 599 / 436 / 136 Регистрация: 22.11.2017 Сообщений: 1,340
	17.08.2019, 20:36 [ТС]	3
	jogano, отличное и развёрнутое объяснение. Спасибо! 0

Взбалтывание контейнера пока его элементы не упорядочатся

Решение