Рассмотрим мерный вектор v, где v i ∈ { 0 , 1 } . Для каждого i мы знаем p i = P ( v i = 1 ) и допустим, что v i независимы. Используя эти вероятности, существует ли эффективный способ итерации по двоичным n- мерным векторам в порядке от наиболее вероятного к наименее вероятному (с произвольным выбором связей) с использованием пространства, сублинейного в выходном размере?
Возьмем для примера . Наиболее вероятным вектором является ( 1 , 0 , 1 ), а наименее вероятным - { 0 , 1 , 0 } .
Для очень малого мы могли бы обозначить каждый из 2 n векторов с его вероятностью и просто отсортировать, но это, конечно, все равно не использовало бы сублинейное пространство.
Близкий вариант этого вопроса ранее задавался по адресу /cs/24123/how-to-iterate-over-vectors-in-order-of-probability .
источник
Ответы:
Далее приведен алгоритм, который использует приблизительно времени и 2 n / 2 пространства.2n 2n/2
Во-первых, давайте рассмотрим проблему сортировки сумм всех подмножеств элементов.n
Рассмотрим эту подзадачу: у вас есть два отсортированных списка длины , и вы хотели бы создать отсортированный список попарных сумм чисел в списках. Вы хотели бы сделать это примерно за O ( м 2 ) времени (выходной размер), но сублинейное пространство. Мы можем достичь O ( м ) пространства. Мы сохраняем приоритетную очередь и извлекаем суммы из приоритетной очереди в порядке возрастания.m O(m2) O(m)
Пусть списки будут и b 1 … b m , отсортированные по возрастанию. Мы берем m сумм a i + b 1 , i = 1 … m и помещаем их в очередь с приоритетами.a1…am b1…bm m ai+b1 i=1…m
Теперь, когда мы вытаскиваем наименьшую оставшуюся сумму из очереди приоритетов, если j < m, мы помещаем сумму a i + b j + 1 в очередь приоритетов. В пространстве преобладает очередь с приоритетами, которая всегда содержит не более m сумм. И время O ( m 2 log m ) , так как мы используем O ( log m ) для каждой приоритетной операции очереди. Это показывает, что мы можем сделать подзадачу в O ( м 2ai+bj j<m ai+bj+1 m O(m2logm) O(logm) время и O ( m ) пространство.O(m2logm) O(m)
Теперь, чтобы отсортировать суммы всех подмножеств из чисел, мы просто используем эту подпрограмму, где список a i является набором сумм подмножеств первой половины элементов, а список b i является набором сумм подмножеств второй половины предметов. Мы можем найти эти списки рекурсивно с помощью того же алгоритма.n ai bi
Теперь рассмотрим исходную проблему. Пусть будет набором координат , равным 0 , а S 1 будет набором координат, равным 1 . Тогда Π я ∈ S 0 р ( v я = 0 ) Π я ∈ S 1 р ( v я = 1 )S0 0 S1 1
Сортировка этих чисел такого же , как сортировка числа , так что мы свели задачу к сортировке суммы подмножеств п элементов.∑i∈S1logp(vi=1)−logp(vi=0) n
источник
(Мы также должны позаботиться о возможных связях, но это не сложно.)
источник
Изменить: этот ответ неверен. Смотрите комментарии для деталей. ~ gandaliter
Вызовите эту рекурсивную функцию в отсортированном списке и пустом векторе.
источник