Tous les sous-ensembles supplémentaires d'une liste en python

Question

Je ne suis pas sûr si 'supplementary' est le bon mot, mais je vais expliquer mon problème avec un exemple. Disons que notre liste est:

[1,2,3,4] 

Ce que je suis en train de trouver est:

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

En d'autres termes, j'essaie d'obtenir toutes les listes de telle sorte qu'ils ont ensemble tous les éléments de la liste initiale.

Merci!

Answer 1

Vous pouvez utiliser Raymond Hettinger's partition recipe pour rechercher toutes les partitions. Je l'ai légèrement modifié pour travailler avec Python3. J'ai également ajouté partition_permutations pour trouver les partitions de toutes les permutations de l'entrée, 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)) 

cède 73 articles:

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

---

noter que partition_permutations traite les objets à l'intérieur de chaque partition en tant non ordonnée. C'est-à-dire, par exemple, [[1,4], [2,3]] et [[2,3], [1,4]] sont traités comme la même partition. Si ce n'est pas ce que vous voulez, puis changer

result = partition_permutations(x) 

à

result = partition_permutations(x, ordered_partitions=True)