Генерация всех подмножеств с ограничениями сопряжения - PullRequest
Новая
       10

Генерация всех подмножеств с ограничениями сопряжения

0 голосов
/ 03 мая 2018

Мне нужно сгенерировать все k-подмножества n-множества с дополнительным ограничением, что некоторые пары элементов должны выбираться либо вместе, либо вообще не выбираться. Чтобы смоделировать это ограничение, я подумал о том, чтобы явно связать эти элементы как 2-кортежи и сохранить остальные как 1-кортежи. Например, давайте предположим, что мне нужно выбрать все 3-элементные подмножества {1, 2, 3, 4, 5} с дополнительными ограничениями на то, что элементы 3 и 4 должны выбираться вместе. Тогда мой новый набор: 

{(1,), (2,), (3, 4), (5,)}

и функцию, которую я хочу написать, нужно сгенерировать: 

{1, 2, 5}, {1, 3, 4}, {2, 3, 4}, {3, 4, 5}.

Есть ли простой способ использования itertools (или, возможно, других модулей python, которых я не знаю) для получения этого результата? Меня не волнует порядок, в котором я получаю эти подмножества.

В случае, если это упрощает вещи: элемент не может быть связан с более чем одним другим элементом (например, (3, 5) не мог бы появиться в качестве дополнительного ограничения в моем примере).

1 Ответ

0 голосов
/ 03 мая 2018

Решение: 

from itertools import combinations, chain

def faster(pairs, others, k):
    for npairs in range(k // 2 + 1):
        for pairs_comb in combinations(pairs, npairs):
            for others_comb in combinations(others, k - npairs * 2):
                yield chain(others_comb, *pairs_comb)

Пояснение:

Пройдите все возможности для количества пар в результате. Например, если k = 5, то не может быть ни пары, ни 5 неограниченных элементов (others), либо 1 пара и 3 других элемента, либо 2 пары и 1 другой элемент. Тогда все комбинации пар и другие могут быть сгенерированы независимо и объединены.

Тест: 

def brute_force(pairs, others, k):
    return [c for c in combinations(chain(others, *pairs), k)
            if all((p1 in c) == (p2 in c) for p1, p2 in pairs)]

def normalise(combs):
    return sorted(map(sorted, combs))

args = ([(3, 4), (1, 2), (6, 7)], [5, 8, 9, 10, 11], 4)
assert normalise(brute_force(*args)) == normalise(faster(*args))

print(normalise(faster(*args)))
...