Как симулировать комбинаторные сочетания (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]

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

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, спасибо, посмотрю

Answer 2

[Rsa97]

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