Играли с дочкой с игру эрудит. Она проходит простые вероятности в школе. Она задала вопрос: какова вероятность в начале партии взять полное слово "какашка". Более формально: есть набор из 130 букв, берёшь 7 случайных, какова вероятность, что из них можно составить "какашка". В наборе 9 'а', 6 'к', и 1 'ш'. Для простоты звёздочки не учитываются.
Моё решение ~ 6.46e-7. Свои формулы пока не раскрою. Решение потребовало знание формул комбинаторики — количество перестановок и факториалы, что они ещё не проходили. Правильное ли решение? Какое самое простое объяснение решения?

Здравствуйте, SuhanovSergey, Вы писали:

SS>Играли с дочкой с игру эрудит. Она проходит простые вероятности в школе. Она задала вопрос: какова вероятность в начале партии взять полное слово "какашка". Более формально: есть набор из 130 букв, берёшь 7 случайных, какова вероятность, что из них можно составить "какашка". В наборе 9 'а', 6 'к', и 1 'ш'. Для простоты звёздочки не учитываются.
SS>Моё решение ~ 6.46e-7. Свои формулы пока не раскрою. Решение потребовало знание формул комбинаторики — количество перестановок и факториалы, что они ещё не проходили. Правильное ли решение? Какое самое простое объяснение решения?

можно по вероятностям пройтись, 6/130 * 9/129 * 5/128 * 8/127 * 1/126 * 4/125 * 7/124 .

Здравствуйте, SomeOne_TT, Вы писали:

SO_>Здравствуйте, SuhanovSergey, Вы писали:

SS>>Играли с дочкой с игру эрудит. Она проходит простые вероятности в школе. Она задала вопрос: какова вероятность в начале партии взять полное слово "какашка". Более формально: есть набор из 130 букв, берёшь 7 случайных, какова вероятность, что из них можно составить "какашка". В наборе 9 'а', 6 'к', и 1 'ш'. Для простоты звёздочки не учитываются.

SO_>можно по вероятностям пройтись, 6/130 * 9/129 * 5/128 * 8/127 * 1/126 * 4/125 * 7/124 .

видимо, я не прав — это формула для последовательного вынимания нужных букв, а у тебя порядок неважен.
Без факториалов, говоришь...

SO_>>можно по вероятностям пройтись, 6/130 * 9/129 * 5/128 * 8/127 * 1/126 * 4/125 * 7/124 .

SO_>видимо, я не прав — это формула для последовательного вынимания нужных букв, а у тебя порядок неважен.
SO_>Без факториалов, говоришь...

А разве твоя формула от порядка зависит?

Допустим, мы рассматриваем просто "ка". Порядок может быть "ка" или "ак", вероятность одинаковая. И это справедливо для слова любой длины.

6/130 * 9/129 == 9/130 * 6/128

Здравствуйте, SuhanovSergey, Вы писали:

SS>Играли с дочкой с игру эрудит. Она проходит простые вероятности в школе. Она задала вопрос: какова вероятность в начале партии взять полное слово "какашка". Более формально: есть набор из 130 букв, берёшь 7 случайных, какова вероятность, что из них можно составить "какашка". В наборе 9 'а', 6 'к', и 1 'ш'. Для простоты звёздочки не учитываются.
SS>Моё решение ~ 6.46e-7. Свои формулы пока не раскрою. Решение потребовало знание формул комбинаторики — количество перестановок и факториалы, что они ещё не проходили. Правильное ли решение? Какое самое простое объяснение решения?

Мое решение спросонок:

Рассмотрим вероятность достать из мешка любую выигрышную комбинацию, например 3к, затем 3а и затем ш:

P1 = 6/130 * 5/129 * 4/ 128 * 9/127 * 8/ 126 * 7/125 * 1/ 124 = (9*8*7*6*5*4*1)/(130*129*128*127*126*125*124).

Как видно, P1 не зависит от порядка доставания косточек из мешка — каждый раз используем одну цифру числителя и одну знаменателя, например если достали первую а, то используем 9 и 130 соответственно.

Всего выигрышных перестановок 7!, ответ 7!*P1 ~ 5.7252e-07

PS Объяснение числа перестановок — размер группы S7. Шучу Первое число можем поставить в 7 позиций, следующее — в 6 и т.п. Всего 7*6*5*...

Здравствуйте, andyp, Вы писали:

A>Всего выигрышных перестановок 7!, ответ 7!*P1 ~ 5.7252e-07

Решение выглядит логично.
Численное моделирование даёт меньшую вероятность ~1.65e-08.

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <numeric>
#include <thread>
#include <atomic>

using namespace std;

const int N = 130;
const int K = 7;
const int K_avail = 6;
const int A_avail = 9;
const int SH_avail = 1;
const long long ITERATIONS_PER_THREAD = 2000000000ll;

bool select(vector<char>& deck, mt19937& generator) {
    auto begin = deck.begin();
    auto end = deck.end();
    size_t left = distance(begin, end);
    uniform_int_distribution<int> distribution;
    int num_random = K;
    while (num_random--) {
        auto r = begin;
        advance(r, distribution(generator, uniform_int_distribution<int>::param_type(0, left)));
        if (*r == '*') {
            return false;
        }
        iter_swap(begin, r);
        ++begin;
        --left;
    }
    return true;
}

bool is_hit(const vector<char>& deck) {
    int k_count = 0;
    int a_count = 0;
    int sh_count = 0;
    for (int i = 0; i < K; ++i) {
        switch (deck[i]) {
            case 'K': ++k_count; break;
            case 'A': ++a_count; break;
            case 'S': ++sh_count; break;
        }
    }
    return k_count == 3 && a_count == 3 && sh_count == 1;
}

void simulate(atomic<int>& hits_count) {
    vector<char> deck(N);
    for (size_t i = 0; i < deck.size(); ++i) {
        deck[i] =
            i < K_avail ? 'K' :
            i < K_avail + A_avail ? 'A' :
            i < K_avail + A_avail + SH_avail ? 'S' :
            '*';
    }
    mt19937 generator;
    shuffle(deck.begin(), deck.end(), generator);
    for (long long i = 0; i < ITERATIONS_PER_THREAD; ++i) {
        if (select(deck, generator) && is_hit(deck)) {
            ++hits_count;
        }
    }
}

int main() {
    atomic<int> hits_count = {0};
    vector<thread> threads;
    for (int i = 0; i < 8; ++i) {
        threads.emplace_back(simulate, ref(hits_count));
    }
    for (auto& t : threads) {
        t.join();
    }
    cout << "hits " << hits_count.load() << endl;
    cout << "probability " << (double)hits_count.load() / (double)(ITERATIONS_PER_THREAD * threads.size()) << endl;
    return 0;
}

Здравствуйте, SuhanovSergey, Вы писали:


SS>Численное моделирование даёт меньшую вероятность ~1.65e-08.

	Код
	SS> SS>#include <iostream> SS>#include <vector> SS>#include <random> SS>#include <algorithm> SS>#include <cmath> SS>#include <math.h> SS>#include <numeric> SS>#include <thread> SS>#include <atomic> SS>using namespace std; SS>const int N = 130; SS>const int K = 7; SS>const int K_avail = 6; SS>const int A_avail = 9; SS>const int SH_avail = 1; SS>const long long ITERATIONS_PER_THREAD = 2000000000ll; SS>bool select(vector<char>& deck, mt19937& generator) { SS> auto begin = deck.begin(); SS> auto end = deck.end(); SS> size_t left = distance(begin, end); SS> uniform_int_distribution<int> distribution; SS> int num_random = K; SS> while (num_random--) { SS> auto r = begin; SS> advance(r, distribution(generator, uniform_int_distribution<int>::param_type(0, left))); SS> if (*r == '*') { SS> return false; SS> } SS> iter_swap(begin, r); SS> ++begin; SS> --left; SS> } SS> return true; SS>} SS>bool is_hit(const vector<char>& deck) { SS> int k_count = 0; SS> int a_count = 0; SS> int sh_count = 0; SS> for (int i = 0; i < K; ++i) { SS> switch (deck[i]) { SS> case 'K': ++k_count; break; SS> case 'A': ++a_count; break; SS> case 'S': ++sh_count; break; SS> } SS> } SS> return k_count == 3 && a_count == 3 && sh_count == 1; SS>} SS>void simulate(atomic<int>& hits_count) { SS> vector<char> deck(N); SS> for (size_t i = 0; i < deck.size(); ++i) { SS> deck[i] = SS> i < K_avail ? 'K' : SS> i < K_avail + A_avail ? 'A' : SS> i < K_avail + A_avail + SH_avail ? 'S' : SS> '*'; SS> } SS> mt19937 generator; SS> shuffle(deck.begin(), deck.end(), generator); SS> for (long long i = 0; i < ITERATIONS_PER_THREAD; ++i) { SS> if (select(deck, generator) && is_hit(deck)) { SS> ++hits_count; SS> } SS> } SS>} SS>int main() { SS> atomic<int> hits_count = {0}; SS> vector<thread> threads; SS> for (int i = 0; i < 8; ++i) { SS> threads.emplace_back(simulate, ref(hits_count)); SS> } SS> for (auto& t : threads) { SS> t.join(); SS> } SS> cout << "hits " << hits_count.load() << endl; SS> cout << "probability " << (double)hits_count.load() / (double)(ITERATIONS_PER_THREAD * threads.size()) << endl; SS> return 0; SS>} SS>

Уверен что к тебя генератор с разным seed во всех нитках стартует? Я стандартным генератором не пользовался, но судя по описанию cppreference, везде один сид используется. Кстати, даже лучший prng может быть чуть неравномерен, что затрудняет ловлю таких хвостов, как в задаче. Ну и, конечно, то, что я в рассуждениях накосячил, никто не отменял.

Здравствуйте, andyp, Вы писали:


A>Уверен что к тебя генератор с разным seed во всех нитках стартует?
Да, seed был один. Все треды делали одно и то же. Пофиксил — https://www.codepile.net/pile/krn47NPp. Результат стал менее "круглым", но не особо поменялся 1.55625e-08.

A>Рассмотрим вероятность достать из мешка любую выигрышную комбинацию, например 3к, затем 3а и затем ш:

Разве эта вероятность не является окончательным ответом? Откуда берутся перестановки?

Здравствуйте, bzig, Вы писали:


B>Разве эта вероятность не является окончательным ответом? Откуда берутся перестановки?

Ты можешь достать из мешка как "какашка" так и "кккаааш"

Здравствуйте, SuhanovSergey, Вы писали:

SS>Да, seed был один. Все треды делали одно и то же. Пофиксил — https://www.codepile.net/pile/krn47NPp. Результат стал менее "круглым", но не особо поменялся 1.55625e-08.

Я должен был поставить свои кривые мозги на первое место в списке причин несоответствия. Там же перестановки с повторениями. P1 нужно умножать на 7!/(3! * 3!): 1.5903e-08.

Здравствуйте, andyp, Вы писали:

A>Здравствуйте, bzig, Вы писали:


B>>Разве эта вероятность не является окончательным ответом? Откуда берутся перестановки?

A>Ты можешь достать из мешка как "какашка" так и "кккаааш"

разве эти числа в знаменателе (9, 8 ...) не учитывают это? Если считать, что все 130 костяшек уникальны, то вероятность вынуть одну конкретную комбинацию 1/130*1/129*...*1/124, не?

Здравствуйте, bzig, Вы писали:

B>разве эти числа в знаменателе (9, 8 ...) не учитывают это? Если считать, что все 130 костяшек уникальны, то вероятность вынуть одну конкретную комбинацию 1/130*1/129*...*1/124, не?

Нет, не учитывают. Ты можешь вытащить костяшки для слова "вобла" 120 способами с равной вероятностью при уникальных костяшках. Вероятность вытаскивания прямо слова "вобла" будет равна 1/130*1/129*..., а вероятность того, что у тебя окажутся нужные буквы, чтобы это слово составить, будет в 120 раз больше.

Здравствуйте, andyp, Вы писали:

A>Мое решение спросонок:

A>Рассмотрим вероятность достать из мешка любую выигрышную комбинацию, например 3к, затем 3а и затем ш:

A>P1 = 6/130 * 5/129 * 4/ 128 * 9/127 * 8/ 126 * 7/125 * 1/ 124 = (9*8*7*6*5*4*1)/(130*129*128*127*126*125*124).

A>Как видно, P1 не зависит от порядка доставания косточек из мешка — каждый раз используем одну цифру числителя и одну знаменателя, например если достали первую а, то используем 9 и 130 соответственно.

A>Всего выигрышных перестановок 7!, ответ 7!*P1 ~ 5.7252e-07

Чуть чуть вы ошиблись. Еще надо разделить на 36.


Мое решение: число способов выбрать 7 букв из 30 равно C(30, 7) = (130*129*128*127*126*125*124)/7!

Подсчитаем, сколько будет выигрышных комбинаций из 7 букв.
Каждая выигрышная комбинация состоит из 3к, 3а и 1ш.
Число способов выбрать 3к из 6к равно C(6, 3) = (6*5*4)/(1*2*3)
Число способов выбрать 3а из 9а равно C(9, 3) = (9*8*7)/(1*2*3)
Число способов выбрать 1ш из 1ш равно C(1, 1) = 1

Для получения общего числа выигрышных комбинаций надо это все просто перемножить.

А для получения вероятности выбрать выигрышную комбинацию, надо число выигрышных комбинаций разделить на общее число комбинаций

Итого 7!*(9*8*7*6*5*4*1)/((130*129*128*127*126*125*124) * 3! *3!).

Т.е ваш ответ, но еще два раза деленный на 3! , т.е на 36.

И у меня получилось ~1.59e-08.

Здравствуйте, baily, Вы писали:

B>Чуть чуть вы ошиблись. Еще надо разделить на 36.

Понял это сегодня утром.

Здравствуйте, SuhanovSergey, Вы писали:

SS>Какое самое простое объяснение решения?

если, вдруг, знает Питон, то что-то вроде:

def p_select_set_from( from_N, *n_from_m) :
    """
    вычисляет вероятность выбрать нужный набор букв в "эрудите"
    from_N -- оставшееся в мешке число фишек
    n_from_m -- набор пар (сколько_осталось_набрать_такой_буквы, сколько_осталось_в_мешке_такой_буквы)
    """
    if not n_from_m :
        return 1. #пустое множество всегда достанется из мешка за 0 действий ;)
    
    p = 0.0
    for i, nm in enumerate( n_from_m ):
        n, m = nm
        assert 1 <= n <= m 
        # условная вероятность выбрать такую фишку -- m/from_N
        # но её ещё нужно умножить на условную вероятность выбрать оставшееся множество
        if n == 1 :
            # такие фишки больше не нужны
            p += m/from_N * p_select_set_from(from_N-1, *n_from_m[:i], *n_from_m[i+1:])
        else :
            # такие фишки ещё нужны, но на 1 меньше и в мешке их останется на 1 меньше тоже
            p += m/from_N * p_select_set_from(from_N-1, *n_from_m[:i], (n-1, m-1), *n_from_m[i+1:])
    return p
    
p_select_set_from( 130, (3,9), (3,6), (1,1))

Печатает 1.5903430733516207e-08

p. s.
А если вдруг знает-знает, то можно по-модному, по-молодёжному:

def f(from_N, *n_from_m) :
    return 1. if not n_from_m else sum( nm[1]* (
                f(from_N-1, *n_from_m[:i],                     *n_from_m[i+1:]) 
            if nm[0] == 1 else 
                f(from_N-1, *n_from_m[:i], (nm[0]-1, nm[1]-1), *n_from_m[i+1:])
                                               ) for i, nm in enumerate(n_from_m) ) / from_N

Здравствуйте, bzig, Вы писали:

B>А разве твоя формула от порядка зависит?
B>Допустим, мы рассматриваем просто "ка". Порядок может быть "ка" или "ак", вероятность одинаковая. И это справедливо для слова любой длины.
B>6/130 * 9/129 == 9/130 * 6/128

Вероятность за два вытягивания вытащить "ак" равна вероятности вытащить "ка". А вот вероятность за два вытягивания вытащить "или ка или ак" вдвое выше.