Подсчитайте количество путей в DAG с длиной K
У меня есть DAG с 2 ^ N узлами, со значениями от 0 до 2 ^ N-1. Существует ребро от х до у, если х < y и x (xor) y = 2 ^ p, x и y — значения узлов, а p — неотрицательное целое число.
Поскольку N может достигать 100000, создание графика и выполнение подсчета займет много вычислительного времени. Есть ли способ подсчитать пути с определенной длиной K (где K — это число ребер между двумя узлами), иначе говоря, существует ли какое-то уравнение для такого рода подсчетов?
заранее спасибо
Решение
У Майкла есть хорошие идеи, но я не уверен, что следую всему его аргументу. Вот мое решение.
Допустим, N = 4, K = 2. Таким образом, узлы варьируются от 0 (00002) до 15 (11112).
Теперь давайте рассмотрим узел 2 (00102). Там преимущество от 2 до 3 (00112) потому что 2 < 3 и xor (2,3) = 1 = 20. Там также преимущество от 2 до 6, потому что 2 < 6 и xor (2,6) = 4 = 22. И есть преимущество от 2 до 10, потому что 2 < 10 и xor (2,10) = 8 = 23.
Для обобщения: для любого x рассмотрим все 0 битов в x. Переключив любой из 0 битов на 1, вы получите число y, которое больше x и отличается от x на один бит. Так что есть грань от х до этого у.
Число 1 бит в х обычно называется подсчет населения из х. Я буду использовать pop (x) для обозначения количества населения x.
Мы имеем дело с N-битными числами (когда мы включаем начальные нули), поэтому число 0 битов в x равно N — pop (x).
Давайте использовать термин «J-путь »означает путь длины J. Мы хотим посчитать количество K-путей.
Каждый узел x имеет N — pop (x) исходящих ребер. Каждый из этих ребер является 1-дорожкой.
Давайте рассмотрим узел 5 (01012). Узел 5 имеет преимущество до 7 (01112), а узел 7 имеет ребро до 15 (11112). Узел 5 также имеет преимущество до 13 (11012), а узел 13 имеет ребро до 15 (11112). Таким образом, есть два 2-х пути из узла 5: 5-7-15 и 5-13-15.
Далее давайте посмотрим на узел 2 (00102) снова. Узел 2 имеет преимущество до 3 (00112), который имеет ребра до 7 (01112) и 11 (10112). Узел 2 также имеет ребро к узлу 6 (01102), который имеет ребра до 7 (01112) и 14 (11102). Наконец, узел 2 имеет ребро к узлу 10 (10102), который имеет ребра до 11 (10112) и 14 (11102). В целом, есть два 2-пути из узла 2: 2-3-7, 2-3-11, 2-6-7, 2-6-14, 2-10-11 и 2-10-14 ,
Паттерн таков, что для любого узла x с битами z, установленными в ноль, где z ≥ K, есть некоторые K-пути из x. Чтобы найти K-путь из x, вы выбираете любой K из нулевых битов. Переключение этих битов в 1, один за другим, дает вам путь. Вы можете перевернуть биты в любом порядке; каждый заказ дает свой путь.
Когда вы хотите выбрать k предметов, в определенном порядке, из набора из n предметов, это называется упорядоченным образцом без замены, и есть п! / (н-к)! способы сделать это. Это часто пишут NпК, но здесь легче набрать P (n, k).
Таким образом, узлы, которые имеют ровно 2 нулевых бита, имеют P (2,2) = 2! / (2-2)! = 2 2 пути из них. (Обратите внимание, что 0! = 1.) Узлы, которые имеют ровно 3 нулевых бита, имеют P (3,2) = 3! / 1! = 6 2-х путей из них. Узел, имеющий ровно 4 нулевых бита, имеет P (4,2) = 4! / 2! = 12 2-х путей из него. (Поскольку я использую N = 4 для примера, есть только один узел с ровно 4 нулевыми битами, который является узлом 0.)
Но тогда нам нужно знать, сколько узлов имеют ровно 2 нулевых бита? Хорошо, когда есть n элементов на выбор, и мы хотим выбрать k из них, и мы не заботиться о порядке выбранных товаров, который называется неупорядоченным образцом без замены, и их здесь n! / (k! (n-k)!) способы сделать это. Это называется «n выбирать k», и обычно оно написано так, что я не могу воспроизвести при переполнении стека, поэтому я напишу его как C (n, k).
Для нашего примера с N = 4, есть C (4,2) = 6 узлов с ровно 2 битами, установленными на ноль. Этих узлов 3 (00112), 5 (01012), 6 (01102), 9 (10012) 10 (10102) и 12 (11002). Каждый из этих узлов имеет P (2,2) 2-пути из него, так что это означает, что C (4,2) * P (2,2) = 6 * 2 = 12 2-путей из узлов с точно два 0 бита.
Тогда есть C (4,3) = 4 узла с точно 3 битами, установленными в ноль. Эти узлы 1 (00012), 2 (00102), 4 (01002) и 8 (10002). Каждый из этих узлов имеет P (3,2) 2-пути из него, поэтому есть C (4,3) * P (3,2) = 4 * 6 = 24 2-пути из узлов с ровно тремя 0 биты.
Наконец, существует узел C (4,4) = 1 с ровно 4 битами, установленными на ноль. Этот узел имеет P (4,2) = 12 2-путей из него.
Таким образом, общее число 2-путей, когда N = 4, равно C (4,2) * P (2,2) + C (4,3) * P (3,2) + C (4,4) * P ( 4,2) = 12 + 24 + 12 = 48.
Для общих N и K (где K ≤ N) число K-путей является суммой C (N, z) * P (z, K) для K ≤ z ≤ N.
Я могу напечатать это в Wolfram Alpha (или Mathematica) следующим образом:
Sum[n!/(z! (n - z)!) z!/(z - k)!, {z, k, n}]
2^(n-k) n! / (n-k)!
Другие решения
Заявленная проблема, кажется, эквивалентна этой:
Рассмотрим множество всех возможных двоичных строк длины N. Рассмотрим операцию Fi, которая переворачивает i-й бит с 0 на 1. Для строк x & у обозначает | х | количество установленных бит, х
Легко видеть, что можно получить y из x серией ровно K операций Fi тогда и только тогда, когда (x, y) K-допустимо. Более того, если мы фиксируем x и суммируем по всем y так, что (x, y) K-допустимо, мы получаем (N- | x |)!
Наконец, нам нужно сложить по всем x с помощью | x |<= (N-K). Для данного выбора | x | у нас есть N! / (N- | x |)! | x |! Возможные варианты х. Объедините с вышеизложенным, и вы получите это для заданного | x | Есть N! / | x |! возможные пути.
Обозначим | x | = M, где M от 0 до N-K, а ваш ответ — сумма по всем M из N! / M!