python 中列表的所有补充子集

Question

我不确定 'supplementary' 是否正确，但我会用一个例子来解释我的问题。假设我们的列表是：

[1,2,3,4]

我要查找的是：

[1], [2], [3], [4]
[1,2], [3], [4]
[1,3], [2], [4]
...
[1,2], [3,4]
[1,3], [2,4]
...
[1,2,3], [4]
[1,2,4], [3]
...
[1,2,3,4]

换句话说，我尝试获取所有列表，使它们一起包含初始列表的所有元素。

谢谢！

Answer 1

您可以使用 Raymond Hettinger's partition recipe 来查找所有分区。我稍微修改了它以使用 Python3。我还添加了 partition_permutations 来查找输入的所有排列的分区，x。

import pprint
import itertools as IT

def partition(iterable, chain=IT.chain, map=map):
    """
    http://code.activestate.com/recipes/576795/ (Raymond Hettinger)
    >>> list(partition('abcd'))
    [['abcd'],
     ['a', 'bcd'],
     ['ab', 'cd'],
     ['abc', 'd'],
     ['a', 'b', 'cd'],
     ['a', 'bc', 'd'],
     ['ab', 'c', 'd'],
     ['a', 'b', 'c', 'd']]
    """
    s = iterable if hasattr(iterable, '__getitem__') else tuple(iterable)
    n = len(s)
    first, middle, last = [0], range(1, n), [n]
    getitem = s.__getitem__
    return [list(map(getitem, map(slice, chain(first, div), chain(div, last))))
            for i in range(n) for div in IT.combinations(middle, i)]

def partition_permutations(iterable, ordered_partitions=False):
    result = set()
    for perm in IT.permutations(iterable):
        for item in partition(perm):
            if ordered_partitions:
                result.add(tuple(item))
            else:
                result.add(tuple(sorted(item)))
    result = [list(map(list, item)) for item in result]
    result = sorted(result)
    return result


x = [1,2,3,4]
result = partition_permutations(x, ordered_partitions=True)
pprint.pprint(result)
print(len(result))

产生 73 个项目：

[[[1], [2], [3], [4]],
 [[1], [2], [3, 4]],
 [[1], [2], [4, 3]],
 [[1], [2, 3], [4]],
 [[1], [2, 3, 4]],
 [[1], [2, 4], [3]],
 [[1], [2, 4, 3]],
 [[1], [3], [4, 2]],
 [[1], [3, 2], [4]],
 [[1], [3, 2, 4]],
 [[1], [3, 4, 2]],
 [[1], [4, 2, 3]],
 [[1], [4, 3, 2]],
 [[1, 2], [3], [4]],
 [[1, 2], [3, 4]],
 [[1, 2], [4, 3]],
 [[1, 2, 3], [4]],
 [[1, 2, 3, 4]],
 [[1, 2, 4], [3]],
 [[1, 2, 4, 3]],
 [[1, 3], [2], [4]],
 [[1, 3], [2, 4]],
 [[1, 3], [4, 2]],
 [[1, 3, 2], [4]],
 [[1, 3, 2, 4]],
 [[1, 3, 4], [2]],
 [[1, 3, 4, 2]],
 [[1, 4], [2], [3]],
 [[1, 4], [2, 3]],
 [[1, 4], [3, 2]],
 [[1, 4, 2], [3]],
 [[1, 4, 2, 3]],
 [[1, 4, 3], [2]],
 [[1, 4, 3, 2]],
 [[2], [3], [4, 1]],
 [[2], [3, 1], [4]],
 [[2], [3, 1, 4]],
 [[2], [3, 4, 1]],
 [[2], [4, 1, 3]],
 [[2], [4, 3, 1]],
 [[2, 1], [3], [4]],
 [[2, 1], [3, 4]],
 [[2, 1], [4, 3]],
 [[2, 1, 3], [4]],
 [[2, 1, 3, 4]],
 [[2, 1, 4], [3]],
 [[2, 1, 4, 3]],
 [[2, 3], [4, 1]],
 [[2, 3, 1], [4]],
 [[2, 3, 1, 4]],
 [[2, 3, 4, 1]],
 [[2, 4], [3, 1]],
 [[2, 4, 1], [3]],
 [[2, 4, 1, 3]],
 [[2, 4, 3, 1]],
 [[3], [4, 1, 2]],
 [[3], [4, 2, 1]],
 [[3, 1], [4, 2]],
 [[3, 1, 2], [4]],
 [[3, 1, 2, 4]],
 [[3, 1, 4, 2]],
 [[3, 2], [4, 1]],
 [[3, 2, 1], [4]],
 [[3, 2, 1, 4]],
 [[3, 2, 4, 1]],
 [[3, 4, 1, 2]],
 [[3, 4, 2, 1]],
 [[4, 1, 2, 3]],
 [[4, 1, 3, 2]],
 [[4, 2, 1, 3]],
 [[4, 2, 3, 1]],
 [[4, 3, 1, 2]],
 [[4, 3, 2, 1]]]

请注意 partition_permutations 将每个分区内的项目视为无序的。也就是说，例如 [[1,4], [2,3]] 和 [[2,3], [1,4]] 是视为同一个分区。如果这不是您想要的，请更改

result = partition_permutations(x)

至

result = partition_permutations(x, ordered_partitions=True)

python 中列表的所有补充子集

All supplementary subsets of a list in python

python

combinations

subset

combinatorics

python-3.x