У меня есть список с некоторыми элементами и вы хотите перебрать все возможные способы разделить этот список на два списка. Под этим я подразумеваю все комбинации, поэтому порядок не имеет значения (т.е. Элементы 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.
Есть ли более быстрый и элегантный (более короткий/более питонический) способ сделать это?
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]])
Первая часть может быть однострочной с учетом вложенных списков, таких как:
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 их каждый раз.
Просто расширяя решение @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'], []]]
Для полноты вы также можете свернуть набор элементов питания в два раза для получения желаемых результатов. Например, рассмотрите силовую схему {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))