Python 获取一个列表的所有子集

发表评论
5039 views

 ›
Python 获取一个列表的所有子集 
from itertools import chain, combinations

def powerset(iterable):
    """
    powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
    """
    xs = list(iterable)
    # note we return an iterator rather than a list
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))

使用示例：

list(powerset("abc"))
>>> [(), ('a',), ('b',), ('c',), ('a', 'b'), ('a', 'c'), ('b', 'c'), ('a', 'b', 'c')]

原理说明：

itertools 是 python 内建的为了高效循环而创建迭代器的函数，官方文档

chain.from_iterable(iterable)

用于创建一个迭代器,从一个单独的可迭代参数中得到链式输入，该参数是延迟计算的。

例如： # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F

itertools.combinations(iterable, r)

返回由输入 iterable 中元素组成长度为 r 的子序列。组合按照字典序返回。所以如果输入 iterable 是有序的，生成的组合元组也是有序的。此外即使元素的值相同，不同位置的元素也被认为是不同的。如果元素各自不同，那么每个组合中没有重复元素。

例如：# combinations('ABCD', 2) --> AB AC AD BC BD CD

chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))

综上述所得，则上面函数相当于，将输入的可迭代元素，首先转换为 list 类型，然后使用列表推导式，遍历元素最大长度下，所有长度的子集，然后拼合返回。