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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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)

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

Wataru,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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