Tất cả các khả năng chia danh sách thành hai danh sách

Question

Tôi có một danh sách với một số thành phần và muốn lặp qua tất cả các cách có thể để chia danh sách này thành hai danh sách. Bởi vì tôi có nghĩa là tất cả các kết hợp, do đó, thứ tự không quan trọng (tức là Element 1 và 3 có thể nằm trong một danh sách và Element 2 trong danh sách kia). Hiện nay tôi làm điều đó như thế này, nơi facs là danh sách ban đầu của tôi:

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

Vì vậy, tôi về cơ bản tạo ra một danh sách dài 2^(len(facs)-1) và điền nó với tất cả các kết hợp có thể có của những người thân và số không. Sau đó tôi 'che phủ' mọi mẫu với facs, ngoại trừ phần tử cuối cùng của facs luôn ở trong l1, như tôi sẽ nhận được mọi kết quả hai lần, vì tôi xử lý hai danh sách giống nhau, bất kể danh sách nào là l1 hoặc l2.

Có cách nào nhanh hơn và thanh lịch hơn (ngắn hơn/nhiều hơn) để thực hiện việc này không?

Answer 1

itertools có product() có thể được sử dụng để tạo mặt nạ và izip() có thể kết hợp danh sách để lọc dễ dàng. Là một phần thưởng, vì chúng trả về các trình lặp, chúng không sử dụng nhiều bộ nhớ.

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

phần Đầu tiên có thể được một lót bằng comprehensions danh sách lồng nhau như thế này:

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

Đối với phần thứ hai, bạn không thể làm một danh sách hiểu vì có 2 danh sách, nhưng bạn có thể làm một biểu ternary để chọn danh sách để thêm vào.

Và bạn có thể zip cả pattern và facs danh sách để tránh chơi với các chỉ số:

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

tất nhiên bạn phải sử dụng l1 và l2 trong phiên, bởi vì bạn thiết lập lại chúng mỗi lần.

Answer 3

Chỉ cần mở rộng giải pháp @Ouroborus sử dụng filter s và giữ các kết quả với nhau:

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

Để hoàn chỉnh, bạn cũng có thể fold the powerset in half để tạo ra kết quả mong muốn. Ví dụ, hãy xem xét Powerset của {A, B, C} để colexicographic theo bitmask tương ứng của mỗi tập hợp con:

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

Nếu bạn xoay chiều kim đồng hồ nửa đầu bằng 90 độ, và xoay nửa ngược chiều kim đồng bằng 90 độ, và sau đó dòng họ lên, bạn có hai cột của tập hợp con và mỗi hàng tạo thành một phân vùng của tập hợp ban đầu. Chúng ta có thể thực hiện điều này "gấp" bằng cách nén quyền hạn với đảo ngược chính nó và lấy một nửa số cặp con được tạo ra. Mất một nửa đảm bảo rằng chỉ có các phân vùng duy nhất được tạo (ví dụ: [['two', 'three'], ['one']] và [['one'], ['two', 'three']] là cùng một phân vùng), giả sử trình tự ban đầu là riêng biệt.

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

Trong khi nó không phải là rất hữu ích, nó làm cho một giải pháp dễ thương. Dưới đây là một vài biến thể - thay vì chạy hai trình chuyển đổi quyền hạn ngược lại - chỉ cần tạo trực tiếp phần bổ sung cho mỗi tập hợp con.

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