在列表中找到 2^n -2 个元素组合

Question

我有以下列表：

list1 = ['g1','g2','g3','g4']

我想找到 2^n-2 组合，其中 n 是列表中的项目总数。对于 n = 4，结果应该是 2^4 -2 = 14，即 14 种组合。

组合是：

[[['g1'],['g2','g3','g4']],[['g2'],['g1','g3','g4']], [['g3'],['g1','g2','g4']],['g4'],['g1','g2','g3']],[['g1','g2'],['g3','g4']],[['g1','g3'],['g2','g4']],[['g1','g4'],['g3','g4']],[['g2','g3'],['g1','g4']],
[['g2','g4'],['g1','g3']],[['g3','g4'],['g1','g2']],[['g1','g2','g3'],['g4']],[['g2','g3','g4'],['g1']],[['g3','g4','g1'],['g2']],[['g4','g1','g2'],['g3']]]

我知道一种方法：在第一次迭代中，取单个元素并将其放入列表和第二个列表中的其他元素：['g1'],['g2','g3','g4'] 在第二次迭代中，在列表中取 2 个元素，在第二个列表中取其他元素。 ['g1','g2'],['g1','g4'] 还有其他方法吗？我正在 python 中编写此程序。我的方法是昂贵的。有没有什么库方法可以快速做到这一点。

Answer 1

这是使用 itertools

的函数式方法

import itertools as iter

list1 = ['g1', 'g2', 'g3', 'g4']
combinations = [iter.combinations(list1, n) for n in range(1, len(list1))]
flat_combinations = iter.chain.from_iterable(combinations)
result = map(lambda x: [list(x), list(set(list1) - set(x))], flat_combinations)
# [[['g1'], ['g4', 'g3', 'g2']], [['g2'], ['g4', 'g3', 'g1']], [['g3'], ['g4', 'g2', 'g1']],...
len(result)
# 14

Answer 2

itertools.combinations(iterable, r)

Return r length subsequences of elements from the input iterable. Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

from itertools import combinations
list1 = ['g1','g2','g3','g4']
for n in range(1,len(list1)):
    for i in combinations(list1,n):
        print(set(i), set(list1) - set(i))

输出：

{'g1'} {'g2', 'g3', 'g4'}
{'g2'} {'g1', 'g3', 'g4'}
{'g3'} {'g1', 'g2', 'g4'}
{'g4'} {'g1', 'g2', 'g3'}
{'g1', 'g2'} {'g3', 'g4'}
{'g1', 'g3'} {'g2', 'g4'}
{'g1', 'g4'} {'g2', 'g3'}
{'g2', 'g3'} {'g1', 'g4'}
{'g2', 'g4'} {'g1', 'g3'}
{'g3', 'g4'} {'g1', 'g2'}
{'g1', 'g2', 'g3'} {'g4'}
{'g1', 'g2', 'g4'} {'g3'}
{'g1', 'g3', 'g4'} {'g2'}
{'g2', 'g3', 'g4'} {'g1'}

你可以试试这个

Answer 3

我喜欢中国程序员的解决方案（我猜）。这是我自己的解决方案：

import itertools


def flatten(*z):
    return z


list1 = ['g1','g2','g3','g4']

sublists = []
for i in range(1, len(list1)):
    sublists.extend(itertools.combinations(list1, i))

pairs = []
for a, b in itertools.product(sublists, sublists):
    if len(a) + len(b) == len(list1) and \
    len(set(flatten(*a, *b))) == len(list1):
        pairs.append((a, b))

print(pairs, len(pairs))

在列表中找到 2^n -2 个元素组合

find 2^n -2 combinations of elements in a list

python

list

combinations

apriori