Set partitions en Python

Question

j'ai un tableau de [1,2,3]

Je veux faire toutes les combinaisons possibles en utilisant tous les éléments du tableau:

Résultat:

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

Answer 1

Contrairement à mes commentaires ont suggéré, J'ai été incapable de trouver rapidement une solution relativement rapide fondée sur itertools! Edit: ce n'est plus tout à fait vrai, j'ai une solution assez courte (mais lente et illisible) en utilisant largement itertools, voir la fin de la réponse. C'est ce que j'ai obtenu à la place:

L'idée est que nous trouvons toutes les combinaisons d'entiers qui s'ajoutent à la longueur de la liste, et ensuite obtenir des listes avec des tranches de cette longueur.

E.g. pour une liste de longueur 3, les combinaisons, ou partitions, sont (3), (2, 1), (1, 2) et (1, 1, 1). Nous retournons donc les 3 premiers éléments de la liste; les 2 premiers et ensuite les 1 suivants; le premier 1 puis le suivant 2 et le premier 1, puis le suivant 1, puis le suivant 1.

J'ai obtenu le code pour le partitionnement entier de here. Cependant, les fonctions de partition ne renvoient pas toutes les permutations des partitions (c.-à-d. Pour 3 il retournera juste (3), (2, 1) et (1, 1, 1) donc nous devons appeler itertools.permutations sur chacune des partitions . Il nous faut donc supprimer les doublons - tout comme permutations([1, 2, 3]) est [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]];.. permutations([1, 1, 1]) est [[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]] un moyen facile d'éliminer les doublons est en tournant chaque liste de tuples dans un set

tout ce qui reste est d'obtenir des tranches de la liste la . pour les longueurs dans le tuple par exemple, f([1, 2, 3], [0, 0, 1, 2, 1, 0]) va [[0], [0, 1], [2, 1, 0]]

Ma définition de c'est ceci:.

def slice_by_lengths(lengths, the_list): 
    for length in lengths: 
     new = [] 
     for i in range(length): 
      new.append(the_list.pop(0)) 
     yield new 

Maintenant, nous tout combiner:

def subgrups(my_list): 
    partitions = partition(len(my_list)) 
    permed = [] 
    for each_partition in partitions: 
     permed.append(set(itertools.permutations(each_partition, len(each_partition)))) 

    for each_tuple in itertools.chain(*permed): 
     yield list(slice_by_lengths(each_tuple, deepcopy(my_list))) 

>>> for i in subgrups(my_list): 
     print(i) 

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

De plus, vous devez faire import itertools et from copy import deepcopy en haut du programme ainsi.

Editer: votre sortie n'est pas claire. Je supposais que vous vouliez la fonction que je vous ai donnée, mais votre sortie contient également [[1,3],[2]], où les éléments dans la sortie sont dans un ordre différent, contrairement au reste de votre sortie suggérée (je me suis permis de supposer que vous voulez vraiment [[1, 2], [3]] pas [[1, 2], 3]).

C'est-à-dire, je suppose que ce que vous vouliez dire donner en sortie était la suivante:

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

Si, en réalité, il était le suivant:

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

Ensuite, il vous suffit d'appeler subgrups pour chaque permutation en trois longueurs de la liste originale, p.ex. pour chaque permutation en itertools.permutations(my_list, len(my_list)).

Modifier: Maintenant, pour tenir ma promesse d'une courte solution basée itertools. Attention - il peut être à la fois illisible et lent.

D'abord, nous remplacer slice_by_lengths par ceci:

def sbl(lengths, the_list): 
    for index, length in enumerate(lengths): 
     total_so_far = sum(lengths[:index]) 
     yield the_list[total_so_far:total_so_far+length] 

Puis de this réponse nous obtenons notre fonction de partitionnement entier:

def partition(number): 
    return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)} 

Cette fonction obtient en fait toutes les permutations des partitions entières pour nous, nous n'avons pas besoin

for each_partition in partitions: 
    permed.append(set(itertools.permutations(each_partition, len(each_partition)))) 

plus. Cependant, il est beaucoup plus lent que ce que nous avions auparavant, car il est récursif (et nous l'implémentons en Python).

Ensuite, nous venons de mettre ensemble:

def subgrups(my_list): 
    for each_tuple in partition(len(my_list)): 
     yield list(slice_by_lengths(each_tuple, deepcopy(my_list))) 

ou moins lisible, mais sans les définitions de fonction:

def subgrups(my_list): 
    for each_tuple in (lambda p, f=lambda n, g: 
          {(x,) + y for x in range(1, n) for y in g(n-x, g)} | {(n,)}: 
           f(p, f))(len(my_list)): 
     yield list(my_list[sum(each_tuple[:index]):sum(each_tuple[:index])+length] for index, length in enumerate(each_tuple)) 

qui est une définition de fonction et deux lignes, donc assez proche de ce que je a déclaré à l'origine (bien que beaucoup moins lisible et beaucoup plus lent)!

(fonctions appelées subgrups parce que la question posée à l'origine de trouver « tous subgrups »)

Answer 2

Depuis cette belle question a été ramené à la vie, voici une réponse fraîche.

Le problème est résolu récursive: Si vous avez déjà une partition de éléments n-1, comment utilisez-vous pour partitionner n éléments? Placez l'élément n dans l'un des sous-ensembles existants ou ajoutez-le en tant que nouveau sous-ensemble singleton. C'est tout ce qu'il faut; pas itertools, pas de jeux, pas de sorties répétées, et un total de seulement n appels à partition():

def partition(collection): 
    if len(collection) == 1: 
     yield [ collection ] 
     return 

    first = collection[0] 
    for smaller in partition(collection[1:]): 
     # insert `first` in each of the subpartition's subsets 
     for n, subset in enumerate(smaller): 
      yield smaller[:n] + [[ first ] + subset] + smaller[n+1:] 
     # put `first` in its own subset 
     yield [ [ first ] ] + smaller 


something = list(range(1,5)) 

for n, p in enumerate(partition(something), 1): 
    print(n, sorted(p)) 

Sortie:

1 [[1, 2, 3, 4]] 
2 [[1], [2, 3, 4]] 
3 [[1, 2], [3, 4]] 
4 [[1, 3, 4], [2]] 
5 [[1], [2], [3, 4]] 
6 [[1, 2, 3], [4]] 
7 [[1, 4], [2, 3]] 
8 [[1], [2, 3], [4]] 
9 [[1, 3], [2, 4]] 
10 [[1, 2, 4], [3]] 
11 [[1], [2, 4], [3]] 
12 [[1, 2], [3], [4]] 
13 [[1, 3], [2], [4]] 
14 [[1, 4], [2], [3]] 
15 [[1], [2], [3], [4]]