将列表拆分为两个列表的所有可能性

Question

我有一个包含一些元素的列表，并且想要遍历所有可能的方法将此列表分成两个列表。我的意思是所有组合，所以顺序无关紧要（即元素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。

有没有更快，更优雅（更短/更pythonic）的方式来做到这一点？

Answer 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]]) 

Answer 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的

，因为你每次都重新设置。

Answer 3

使用filter坚称我伸出@Ouroborus解决方案，结果呆在一起：

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'], []]] 

Answer 4

为了完整起见，你也可以fold the powerset in half产生预期的效果。例如，根据每个子集的相应位掩码考虑{A, B, C}的幂在colexicographic顺序：

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

如果通过90度上半年顺时针方向旋转，并通过90度逆时针旋转下半年，然后行之你有两列子集，每行形成原始集合的一个分区。我们可以通过将powerset与其自身相反的方式进行压缩并将生成的子集对中的一半进行压缩来实现这种“折叠”。假定原始序列本身是不同的，则取半数确保仅生成唯一分区（例如，[['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)) 

虽然它不是非常有用，它使一个可爱的解决方案。这里有几个变体 - 不是反向运行两个powerset迭代器，而是直接为每个子集生成补集。

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))