Как симулировать комбинаторные сочетания (C(k, n)) за O(1) памяти?

Question

[floppa322]

Начну с примера: В течение недели независимо друг от друга происходят 4 события. Найдите вероятность, что все 4 события произойдут в разные дни недели.

Далее "событие" будет упоминаться в смысле объекта из задачи, а не теории вероятности.
Задачу можно решить двумя способами: с пронумерованными событиями и нет.

1. С пронумерованными событиями: всего 7^4 последовательностей, из них нам подходит 7*6*5*4 последовательностей, вероятность равна 0.35
2. Непронумерованные события: всего наборов C(4, 10) (сочетания с повторами), нужных наборов - C(4, 7), вероятность равна 0.16(6)

Пример кода, симулирующего 1-й случай: код. Тут nextInt() за внутренний цикл генерирует слово алфавита из 7 букв длины 4.

А вот пример кода для 2-го случая, тут просто генерируются "почти все" наборы, а затем выбирается случайный из них, но наборы хранятся в памяти, в отличие от 1-го случая и занимают O(n) памяти, где n - количество наборов, что в случаи комбинаторных функций экспоненциальная величина

Можно ли без костылей просимулировать C-шки, а не A-шки ? Ведь, если пользоваться методами генерации очередного числа случайного вроде nextInt, у нас будет некоторое слово из некоторого алфавита, что является размещением(некоторой пронумерованной последовательностью, а не набором), а не сочетанием

Answer 1

[Wataru]

Вам не нужно их симулировать. Вам нужно их подсчитать. Есть же формулы, на той же википедии посмотрите. Через факториалы. Считается это несколькими циклами прямо в одной переменной. Только аккуратно с большими числами, могут быть переполнения, если у вас нет длинной арифметики в языке.

Edit: Если, все-таки, хочется именно случайно сочетание сгенерировать, то вот алгоритм, основанный на reservoir sampling:

int taken = 0;
for (int i = 0; i < n; ++i) {
  if (rand()*(n-i) < k-taken) {
    ++taken;
    // Взять элемент i.
  }
}

Comments

[floppa322]

Ну я рассматривал симуляцию, как раз, как доп. проверку расчётов

[Wataru]

floppa322, Тогда вам нужно что-то вроде reservoir sampling. Гуглите. На каждом этапе вероятность взять текущий элемент зависит от того, сколько у вас элементов осталость и сколько еще надо взять.

int taken = 0;
for (int i = 0; i < n; ++i) {
  if (rand()*(n-i) < k-taken) {
    ++taken;
    // Взять элемент i.
  }
}

[floppa322]

Ну и в целом вопрос был больше про симуляцию вероятностных процессов, именно в контексте того, что в распоряжении есть только генерация одного случайного числа, что в конечном счёте сводится к генерации случайного слова некоторого алфавита(если несколько раз сгенерировать случайное число), а это уже размещения, а не сочетания

[floppa322]

Wataru, спасибо, посмотрю

[floppa322]

Wataru, кажется нашёл, вот. Почему-то с 1го раза не нагуглил

[Wataru]

floppa322, можно и так. Мой метод тоже за O(n) работает, но не требует никакого массива на n элементов, так что он лучше по памяти.

[floppa322]

Wataru, хм, я тогда сразу же перешёл к статье "reservoir sampling", думал что в вашем коде то же самое, но коротко. но вот сейчас проверил ваш сниппет кода, получилось 0.437483, эту вероятность я получал, когда считал, сколько есть нужных перестановок из перестановки длиной 28 символов (7*4 дня недели, с повторением каждого элемента 4 раза): 28!/(4!*4!*4!*4!) (это число всех перестановок, сколько тех, что благоприятные не помню, к сожалению), иными словами, если напихать каждый день недели в массив по 4 раза, пошафлить и взять первые 4 элемента. но у сочетаний должно было получиться, как и написано выше, 0.16(6)

[floppa322]

ой, 28!/(4!*4!*4!*4!*4!*4!*4!) - 7 раз, а не 4

[Wataru]

floppa322, что за вероятность вы считаете? Она не та, что вы ожидаете? Этот код выдаст вам каждое из C(28, 4) сочетаний равновероятно.

[floppa322]

Wataru, ну всего наборов C(4, 10) - сколькими способами можно взять 4 элемента из 7 с повторениями, а нужных C(4, 7) - сколькими способами можно взять 4 элемента из 7 без повторений: C(4, 7)/C(4, 10) = 35/210=0.16(6)

[floppa322]

Wataru, вот, сгенерировал, чтобы яснее было - сверху все элементарные исходы, а ниже - благоприятные

[Wataru]

floppa322, перечитал ваш вопрос, понял. У вас формула неправильная. Всего вариантов 7^4. Каждый независимый эксперимент может выпасть на любой день недели. Хороших же вариантов 4! С(7,4) - выбрали какие дни выпали и в каком порядке. Так что правильная вероятность будет 4!*35/2401 = ~0.34.

Я, правда, так и не понял, как вы считаете вероятность через генерацию сочетания. Но возможно проблема в том, что вам важен еще и порядок элементов в сочетании. Ибо это разные события, когда первый эксперимент выпал на понедельник, а второй - на вторник и когда первый выпал на вторник, а первый - на понедельник. Поэтому после генерации сочетания вам надо полученные 4 элемента случайно перетасовать. Ну, или, действительно, вам лучше подойдет вариант через случайную перестановку массива: сгенерируйте массив от 1 до 7, перемешайте его и берите первые 4 элемента. Тут как раз будет 4! С(7,4) вариантов.

[floppa322]

Wataru, я не совсем явно это описал, но главная мысль была такая: что, если симуляция какого-то вероятностного процесса сводится к наивному вызову чего-то вроде nextInt (ну или любая генерация равномерно распределённого числа), то после этого самого последовательного вызова у нас будет на деле слово алфавита размера k (в данном случае количество дней), и длины n (количество событий в данном примере), но важно заметить, что отношение (вероятность) таких "слов", в которых бы каждая буква встречалось ровно 1 раз, ко всем возможным словам = 0.35, не равно отношению всех наборов, где каждая буква встречается ровно 1 раз ко всем наборам (отличающихся только составом) = 0.16(6)

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

[floppa322]

Wataru,

Я, правда, так и не понял, как вы считаете вероятность через генерацию сочетания.

Ну просто все возможные исходы это все наборы из 7 элементов по 4 элемента, но с повторениями, то есть не только {3, 1, 7, 2}, а ещё и {7, 2, 3, 3}, например. А благоприятные наборы это то же самое, но без повторов, например {2, 1, 7, 6}

Поэтому после генерации сочетания вам надо полученные 4 элемента случайно перетасовать.

Не уверен, что я правильно понял, но, если речь про то, что применить тот же алгоритм, который генерирует "слова", то шафл, применённый после этого алгоритма, не сработает, ведь генерация "слова" уже произошла, но мб я неправильно понял

сгенерируйте массив от 1 до 7, перемешайте его и берите первые 4 элемента. Тут как раз будет 4! С(7,4) вариантов.

Так это же как раз то, что я пытаюсь избежать. Если я правильно понял о чём речь

[Wataru]

floppa322,

Так это же как раз то, что я пытаюсь избежать. Если я правильно понял о чём речь

В алгоритме случайного перемешивания же у вас выплняется swap i-ого значения с j = RandInt()%(i+1). Можно не делать swap, если вам важны только первые k элементов. Сгенерировали j, если j
> Ну просто все возможные исходы это все наборы из 7 элементов по 4 элемента, но с повторениями, то есть не только {3, 1, 7, 2}, а ещё и {7, 2, 3, 3}, например. А благоприятные наборы это то же самое, но без повторов, например {2, 1, 7, 6}

Все равно не понял, как вы счаете вероятность через генерацию случайного объекта. По идее вам надо сгенерировать любые возможные объекты (в задаче из условия у вас не сочетания с повторениями, а просто 7^4 всех слов из алфавита с 7 буквами длины 4). Проверять их на "хорошесть" и увеличивать на 1 счетчик хороших исходов. И всегда увеличивать счетчик попыток. Ответ - счетчик хороших делить на количество попыток. Генерировать при этом хорошие исходы уметь вам совсем не надо.

[Wataru]

floppa322, Почему на 7^4 будет а не C(10, 4), потому что у вас могут быть исходы {3,3,4,7} и {3,4,7,3}, если у вас 4 события могут произойти независимо в один из 7 дней. Два события могут выпасть на среду, но это могут быть первое и второе, а могут быть первое и четвертое. Это разные исходы. Порядок элементов важен. А, если у вас сочетание с повторениями, то порядок был бы не важен.

[floppa322]

Wataru,

в задаче из условия у вас не сочетания с повторениями, а просто 7^4 всех слов из алфавита с 7 буквами длины 4

Видимо я плохо акцентировал внимание на главном, задача тут - довольно второстепенная штука, я просто на примере задачи хотел показать, что её можно решить через A(n,k)/A~(n,k) (размещения/размещения с повторения) и через C(n,k)/C~(n,k) (сочетания/сочетания с повторениями) (хотя для сочетания ей немного условия нужно подправить), но главное это то, что, если бы я захотел запустить симуляцию этих 2-х случаев, то навиная реализация через nextInt(или что-то похожее) привела бы к A(n,k)/A~(n,k), а некостыльюную реализацию для C(n,k)/C~(n,k) я и хотел выяснить

Почему на 7^4 будет а не C(10, 4), потому что у вас могут быть исходы {3,3,4,7} и {3,4,7,3}, если у вас 4 события могут произойти независимо в один из 7 дней. Два события могут выпасть на среду, но это могут быть первое и второе, а могут быть первое и четвертое. Это разные исходы. Порядок элементов важен. А, если у вас сочетание с повторениями, то порядок был бы не важен.

Ну в этом и весь прикол, что наивная реализация и приводит к 7*6*5*4(или 4! С(7,4))/7^4, а хотелось написать C(n,k)/C~(n,k)

[Wataru]

floppa322,

а хотелось написать C(n,k)/C~(n,k)

Тогда задача нужна что-то вроде "есть шляпа, где 28 шаров, по 7 каждого из 4 цветов. Вы тянете оттуда 4 шара. Какова вероятность, что они все разноцветные?"

[floppa322]

Wataru, кстати, даже такое не подходит под сочетания, звучит контринтуитивно, но, если намеренно не создать C~(n,k) шкатулок, в каждой из которых лежало бы множество, отличимое от остальных множеств хотя бы одним элементом, то случай не является сочетаниями

В противном случае, если шарики лежат в "общем" хранилище, то любой i-й шар может быть с любым j-м шаром из выборки, состоящей из k=4 шаров, а значит шары следует нумеровать, а значит это опять задача про размещения.

Случаи с C~(n,k) шкатулками и с "общем" хранилищем шариков фундаментально отличаются тем, что в в каждой из C~(n,k) шкалутол i-й шарик "зафиксирован" со всеми остальными и при каждом эксперименте i-й шарик может быть в наборе только с k-1 фиксированными соседями, а вот во втором случаи i-й шарик может быть с любым n-1 шариком при каждом выполнении эксперимента

Может быть, я где-то ошибаюсь, но вроде всё так

[floppa322]

Wataru,

В противном случае, если шарики лежат в "общем" хранилище, то любой i-й шар может быть с любым j-м шаром из выборки, состоящей из k=4 шаров, а значит шары следует нумеровать, а значит это опять задача про размещения.

Или это даже не размещения. А можно рассуждать следующим образом: разложим в ряд шары из шляпы, это не умоляет общность задачи. Теперь всего таких последовательностей может быть 28!/(4!*4!*4!*4!*4!*4!*4!), а благоприятные последовательности можно посчитать через произведения префиксов на суффиксы: всего нужных префиксов 7*6*5*4, а вот суффиксы здесь это вроде бы (24!/3!*3!*3!*3!*4!*4!*4!)*C(4,7), ну и вероятность как раз должна получиться 0.437483, это и не 0.16(6) и не 0.35

[floppa322]

Wataru, а, не, множитель C(4,7) не нужен:



Здесь 840 это количество всех нужных префиксов длины 4: 7*6*5*4=840

И на всякий случай ещё раз симуляцию скину: именно этого случая, где 0.437674 получается: вот

[floppa322]

Wataru, вроде бы со шляпой из 28 шаров вот как ещё можно рассуждать:

Рассмотрим любой "правильный" набор попарно различных элементов {a,b,c,d} у любого элемента (a,b и т.д.) есть по 4 элемента того же цвета, можно сказать с id, тогда для {a,b,c,d} a,b,c и d каждый из них может быть в 4-х экземплярах, что даёт 4^4 вариантов для {a,b,c,d} а всего таких различных четвёрок C(4,7) = 35, итого благоприятных исходов 4^4*35 = 8960. А всего исходов C(4, 28) = 20475. Итого 8960/20475 = 0.437674

[floppa322]

Wataru, а, это же просто гипергеометрическое распределение

Answer 2

[Rsa97]

Метод Монте-Карло.
Вы просто раз за разом генерируете эти четыре события (фактически, числа от 0000 до 6666) и проверяете, что все цифры в числе разные. Соотношение успешных генераций к общему количеству и даст вероятность. Чем больше генераций (при хорошем ГСЧ), тем точнее результат.

Comments

[floppa322]

Так что в 7-чной системе счисления, что с алфавитом вероятность будет 0.35, а нужна 0.16(6)

[Rsa97]

Кому нужна? Если вы получаете другой ответ, то вы либо решаете нужную задачу, но неверно, либо решаете не ту задачу.

[floppa322]

Rsa97, для неупорядоченных последовательностей она составляет 0.16(6), требуется симуляция именно этого случая, а вы предлагаете способ для упорядоченных последовательностей

[Rsa97]

floppa322, Понятно. Вы решаете не ту задачу, которую привели в начале вопроса.

[floppa322]

Rsa97, так и не предполагалось её решение, там дальше написано, что требуется алгоритм для сочетаний, а не размещений (с помощью nextInt)

вот, кстати он, почему-то изначально не нагуглил

[floppa322]

Rsa97, так тут сразу поставлена задача так что они равновероятны как раз:

Необходимо сгенерировать случайное сочетание из n элементов по k с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.

Ну вот как раз если через какой-нибудь nextInt() делать, то оно в 24 раза будет чаще появляться, чего я и хочу в том числе избежать

[Rsa97]

floppa322, Для простоты будем генерировать наборы чисел, начинающихся с нуля [0, n - 1].
Всего у нас есть ~C(k, n) вариантов сочетаний. Генерируем случайное число в этом диапазоне.
У нас есть n первых чисел. Для первого нуля можно получить ~С(k - 1, n) вариантов, для первой единицы ~C(k - 1, n - 1), для первой двойки ~С(k - 1, n - 2) и так далее. В соответствии с этим выбираем первое число, скажем x0.
Дальше задача сводится к повторению генерации k - 1 числа в диапазоне [x0, n - 1];

Вот примерный код на PHP:

<?php

function Ct($k, $n) {
    $c = 1;
    for ($i = $n; $i <= $n + $k - 1; $i += 1) {
        $c *= $i;
    }

    for ($i = 2; $i <= $k; $i += 1) {
        $c /= $i;
    }

    return $c;
}

function combination($k, $n) {
    $numbers= [];
    $base = 0;
    while ($k > 0) {
        $total = Ct($k, $n - $base);
        $rand = rand(0, $total - 1);
        for ($num = 0; $num < $n - $base; $num += 1) {
            $prob = Ct($k - 1, $n - $base - $num);
            if ($rand < $prob) {
                $numbers[] = $num + $base;
                $k -= 1;
                $base += $num;
                break;
            }

            $rand -= $prob;
        }
    }

    return $numbers;
}

print implode(', ', combination(4, 7)) . "\n";

[floppa322]

Rsa97, спасибо, посмотрю