Задать вопрос
Lite_stream
@Lite_stream

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

Начну с примера: В течение недели независимо друг от друга происходят 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, у нас будет некоторое слово из некоторого алфавита, что является размещением(некоторой пронумерованной последовательностью, а не набором), а не сочетанием
  • Вопрос задан
  • 50 просмотров
Подписаться 1 Простой Комментировать
Решения вопроса 1
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Вам не нужно их симулировать. Вам нужно их подсчитать. Есть же формулы, на той же википедии посмотрите. Через факториалы. Считается это несколькими циклами прямо в одной переменной. Только аккуратно с большими числами, могут быть переполнения, если у вас нет длинной арифметики в языке.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы