將列表拆分爲兩個列表的所有可能性

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