Все возможности разбиения списка на два списка

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

patterns = []
for i in range(2**(len(facs)-1)):
    pattern = []
    for j in range((len(facs)-1)):
        pattern.append(i//(2**j)%2)
    patterns.append(pattern)

for pattern in patterns:
    l1 = [facs[-1]]
    l2 = []
    for i in range(len(pattern)):
        if pattern[i] == 1:
            l1.append(facs[i])
        else:
            l2.append(facs[i])

Итак, я в основном создаю список длины 2^(len(facs)-1) и заполняю его любой возможной комбинацией из них и нулями. Затем я накладываю каждый шаблон на facs, за исключением последнего элемента facs, который всегда находится в l1, так как в противном случае я получал бы каждый результат дважды, поскольку я обрабатываю два списка одинаково, независимо от того, что списки l1 или l2.

Есть ли более быстрый и элегантный (более короткий/более питонический) способ сделать это?

Ответ 1

itertools имеет product(), который можно использовать для создания масок и izip(), которые могли бы комбинировать списки для легкой фильтрации, В качестве бонуса, поскольку они возвращают итераторы, они не используют много памяти.

from itertools import *

facs = ['one','two','three']

l1 = []
l2 = []
for pattern in product([True,False],repeat=len(facs)):
    l1.append([x[1] for x in izip(pattern,facs) if x[0]])
    l2.append([x[1] for x in izip(pattern,facs) if not x[0]])

Ответ 2

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

patterns = [ [ i//(2**j)%2 for j in range(len(facs)-1) ] for i in range(2**(len(facs)-1)) ]

Во второй части вы не можете выполнить понимание списка, так как есть 2 списка, но вы можете сделать тройное выражение, чтобы выбрать список для добавления.

И вы можете zip отображать списки pattern и facs, чтобы избежать воспроизведения с помощью индексов:

for pattern in patterns:
    l1 = [facs[-1]]
    l2 = []
    for fac,pat in zip(facs,pattern):
        (l1 if pat == 1 else l2).append(fac)

конечно, вы должны использовать l1 и l2 во время итерации, потому что вы reset их каждый раз.

Ответ 3

Просто расширяя решение @Ouroborus с помощью filter и сохраняя результаты вместе:

import itertools as it

# itertools recipe
def partition(pred, iterable):
    t1, t2 = it.tee(iterable)
    return it.filterfalse(pred, t1), filter(pred, t2)

>>> facs = ['one','two','three']
>>> [[[x[1] for x in f] for f in partition(lambda x: x[0], zip(pattern, facs))]
...  for pattern in product([True, False], repeat=len(facs))]
[[[], ['one', 'two', 'three']],
 [['three'], ['one', 'two']],
 [['two'], ['one', 'three']],
 [['two', 'three'], ['one']],
 [['one'], ['two', 'three']],
 [['one', 'three'], ['two']],
 [['one', 'two'], ['three']],
 [['one', 'two', 'three'], []]]

Ответ 4

Для полноты вы также можете свернуть набор элементов питания в два раза для получения желаемых результатов. Например, рассмотрите силовую схему {A, B, C} в колликографическом порядке согласно каждой подмножестве соответствующей битмаски:

{}, {A}, {B}, {A, B} | {C}, {A, C}, {B, C}, {A, B, C}

Если вы повернете первую половину по часовой стрелке на 90 градусов и поверните вторую половину против часовой стрелки на 90 градусов, а затем выровняйте их, у вас есть два столбца подмножеств, и каждая строка образует раздел исходного набора. Мы можем реализовать эту "фальцовку", замачивая силовую передачу обратным само по себе и беря половину сгенерированных пар подмножеств. Взятие половины гарантирует, что будут созданы только уникальные разделы (например, [['two', 'three'], ['one']] и [['one'], ['two', 'three']] - один и тот же раздел), предполагая, что исходная последовательность сама по себе различна.

import itertools

def binary_splits(a):
    partitions = zip(powerset_colex(a), powerset_colex(a, reverse = True))
    return itertools.islice(partitions, 1 << len(a) >> 1)

def powerset_colex(a, reverse = False):
    n = len(a)
    bitmasks = range(1 << n)[::-1] if reverse else range(1 << n)
    return (list(itertools.compress(a, iter_bits(bits, n))) for bits in bitmasks)

def iter_bits(n, k):
    return (n >> i & 1 for i in range(k))

В то время как это не очень полезно, оно делает для милого решения. Здесь несколько вариаций, которые вместо двух итераторов с синусоидальным изображением в обратном порядке просто генерируют дополнение для каждого подмножества.

def binary_splits_1(a):
    n = len(a)

    for bitmask in range(1 << n >> 1):
        subset     = itertools.compress(a, iter_bits(+bitmask, n))
        complement = itertools.compress(a, iter_bits(~bitmask, n))
        yield list(subset), list(complement)

def binary_splits_2(a):
    n = len(a)

    def dual_compress(items, bitmask):
        buckets = [], []

        for item, bit in zip(items, iter_bits(bitmask, n)):
            buckets[1 - bit].append(item)

        return buckets

    return (dual_compress(a, bitmask) for bitmask in range(1 << n >> 1))