Pythonのリストのすべての補足サブセット

Question

'補足'が正しい単語であるかどうかはわかりませんが、例を使って問題を説明します。私たちのリストがあるとしましょう：私は見つけることを試みている何

[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個の商品をもたらす：partition_permutationsは 順不同各パーティション内のアイテムを扱うこと

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

---

注意。すなわち、例えば、[[1,4], [2,3]]および[[2,3], [1,4]]は、同じパーティションとして処理された です。それはあなたが望むものでない場合、これは明らかにその質問と重複していない

result = partition_permutations(x) 

result = partition_permutations(x, ordered_partitions=True)