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

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

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

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

Можно ли как-то короче доказать этот факт?

или можно просто сказать, то что у вас написано выше или то что было сказано в комментариях:

Значит Х(i) и У(i) из первого уравнения должны быть точно такие же, как Х(i) и У(i) из второго.

Можно ли как-то короче доказать этот факт?

А это значит, что Х(i) из первого равно Х(i) из второго.

там на самом деле в 5-м пункте это и расписывается, (почему пары решений XY g(f′(y), y) = 0 <=> g(x,y) = 0) просто подробнее немного

Можно ли как-то короче доказать этот факт?

Wataru,

C=A, то можно вместо A написать C везде

да, точно, это как раз то, что я хотел услышать, спасибо )

Можно ли как-то короче доказать этот факт?

jcmvbkbc, ну это вытекает как раз из пункта 5

Можно ли как-то короче доказать этот факт?

Wataru, ну вот я с этим и хотел разобраться как раз, есть ли какое-то простое алгебраическое объяснение, чтобы не получилось как основной теоремой арифметики, что все считают, что это аксиома и её не нужно доказывать

я рассуждал, что если решилось f(x,y) = 0, g(f′(y), y) = 0 то g(f′(y), y) = 0 некоторое другое уравнение и нужно бы показать, что оно является эквивалентным относительно g(x,y) = 0, ну то есть понятно, что можно делать эквивалентные преобразования с одним уравнением, например x= f'(y) <=> f(x,y), тут всё понятно, но вот имея систему, которая является лишь обозначением пересечения множества решений уравнений, просто так на веру утверждать, что подстановка переменной из 1-го уравнения в другое это то же эквивалентное преобразование, что и с x= f'(y) <=> f(x,y), как я понимаю нельзя.

Но вот вопрос-то как раз в этом, если подстановка переменной это что-то совсем простое, как например, отнять по X с обоих частей уравнения и объясняется в одно утверждение, то я как раз и хотел понять в какое :)

Можно ли как-то короче доказать этот факт?

С 6-м пунктом ещё ладно, просто проверил на всякий случай. А вот разве есть какое-то очевидное следствие что g(f′(y), y) = 0 <=> g(x,y) = 0, ради этого же затевался 5-й пункт

Можно ли как-то короче доказать этот факт?

Rsa97, не придирайтесь к словам, пожалуйста, очевидно что в этом контексте это синонимы

Всегда ли DP можно представить в виде DAG?

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

Всегда ли DP можно представить в виде DAG?

Спасибо за ответ

В ДП можно составить граф зависимостей: какие состояния участвуют в вычислении каждого. Это будет DAG. Иначе у вас надо вычислять значения через самих себя и у вас уже не рекуррентные соотношения, а система уравнений.
В некоторых задачах эту систему уравнений можно решать иерархически, по частям, отдельно в каждой компоненте сильной связности. Это немного напоминает ДП, но им не является. Суть ДП в том, что у вас рекуррентные формулы. Это некий более общий алгоритм.

Как-то сталкивался с задачей, где были циклы, но небольшие, компоненты сильной связности были не больше 10 вершин, решались полным перебором, в итоге сворачивались к одной оптимальной вершине и уже потом запускалось дп

Тут вопрос определений. Что считать "представить в виде DAG".

Да, нужно было указать это. Я имел в виду dag как некоторую "проекцию" зависимостей мемоизированных состояний друг на друга через рёбра графа, не учитывая, например, условные операторы, можно сказать "максимальное по включение" множество рёбер

Потому что иногда рекуррентные формулы не симметричные и вам надо, например, одно значение прибавить, другое вычесть. Это не всегда просто определить исключительно в терминах графа. Нельзя сказать что-то вроде "сложить значение во всех вершинах, куда ведут ребра". Но если добавить в этот граф пометки на ребрах или параметры состояний в вершинах, то можно задать нужную функцию (вроде: взять значение для вершины, в которую ведет ребро с пометкой 1 и вычесть значение из вершины, куда ведет ребро с пометкой 2).

Если я правильно понял о чём идёт речь, то можно рассуждать следующим образом: рассмотрим какую-то конкретную задачу (с точностью до набора входных данных). Пусть запустился некоторый алгоритм, использующий мемоизированные данные и завершил вычисление с некоторым результатом. Тогда можно уже после окончания алгорима, не используя условные операторы, построить dag, который потребовался для вычисления результирующего значения (опять же, с точностью до входных данных, т.к. для разных входных данных будут разные рёбра), поскольку вычисления завершены, то мы точно знаем зависимости по мемоизированным состояниям

Более формальный вывод из доказательства по принципу наименьшего числа?

Спасибо за ответ

Просто увидев некоторую симметрию с "домино" индукции, там ведь тоже скипается очевидная часть после базы и шага индукции (что теперь нужно взять базу b0 и подставить в доказынный k-й шаг, применив переход и получив базу b1 и так далее), подумал, что мб здесь так же

Покрытие графа циклами?

https://cstheory.stackexchange.com/questions/46819...

хотя видимо с циклами длины больше 2 есть серьёзные проблемы

Покрытие графа циклами?

Спасибо за ответ

Или можно еще проще: разбиение на циклы равносильно перестановке, которая для каждой вершины задает следующую в цикле. Перестановка равнозначна максимальному паросочетанию.

а, ну да, видимо про маппинг в обе стороны это и имелось в виду

Действительно, полное парсочетание становится циклами. Да, если граф не ориентированный, или содержит "тривальные" циклы (длины 2), то они могут войти в покрытие. Если найдется не полное паросочетание, то в графе будут какие-то непересечающиеся циклы и возможно пути. Он может быть даже не весь покрыт при этом.

как я понял, для неориентированных графов нет алгоритма, чтобы он нет включал циклы длины 2, мб только, если он нашёл дополняющий путь i->j, j->i, какую-то персистентность алгоритму добавить, чтобы он назад до некоторого состояния алгоритма откатился и попробовал пойти "в другую сторону" искать дополняющий путь, но может так получиться, что ему придётся откатиться до самого старта и просто стартовать с другой вершины

Алгоритм для поиска мин. разреза?

Да, точно, забыл про обратные рёбра, спасибо