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

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) 的列表，并用 1 和 0 的所有可能组合填充它。然后我 'overlay' 每个带有 facs 的模式，除了 facs 的最后一个元素总是在 l1 中，否则我会得到每个结果两次，因为我处理两个列表相同，无论列表是 l1 还是 l2.

是否有更快更优雅的（shorter/more pythonic）方法来做到这一点？

Answer 1

第一部分可能是单行嵌套列表理解，如下所示：

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

对于第二部分，您不能进行列表推导，因为有 2 个列表，但您可以对 select 列表进行三元表达式追加。

您可以 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 2

itertools 具有可用于生成掩码的 product() 和可组合列表以便于过滤的 izip()。作为奖励，因为它们 return 迭代器，它们不会使用太多内存。

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 3

只需使用 filters 扩展@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

为了完整起见，您还可以生成所需的结果。例如，考虑 {A, B, C} 的幂集，根据每个子集对应的位掩码按列序排列：

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

如果将前半部分顺时针旋转90度，后半部分逆时针旋转90度，然后排成一行，则有两列子集，每行构成原始集合的一个分区。我们可以通过用自身的反向压缩幂集并取一半生成的子集对来实现这个"folding"。取一半确保只产生唯一的分区（例如 [['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))

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

All possibilities to split a list into two lists

python

combinations

list

permutation