Générer de manière récursive des compositions à partir d'une liste ordonnée

Question

Étant donné une liste ordonnée de 'n' éléments, je souhaite découper la liste pour générer toutes les permutations distinctes de sous-listes une seule fois, tout en maintenant l'ordre de la liste Composition de ma liste d'entrée. (Ce n'est pas la même chose que de calculer toutes les combinaisons possibles de sous-listes possibles à partir de ma liste d'entrées).

Par exemple, la liste d'entrée donné [A,B,C,D], ma sortie serait les 8 listes imbriquées suivantes:

[[A,B,C,D]], [[A,B,C],[D]], [[A,B],[C,D]], [[A,B],[C],[D]], [[A],[B,C],[D]], [[A],[B],[C,D]], [A,[B,C,D]], [[A],[B],[C],[D]]. 

Dessiner un arbre de permutations possibles suggère que ce problème se prêterait à un algorithme récursif, mais je Je ne sais pas comment implémenter ceci en Python pour une vitesse et une efficacité maximales, et je serais très reconnaissant pour vos conseils et vos conseils.

Answer 1

def composition(seq): 
    seq = tuple(seq) 
    for i in range(2**(len(seq)-1)): 
     result = [[seq[0]]] 
     for j in range(len(seq)-1): 
      if i & (1<<j): 
       result.append([seq[j+1]]) 
      else: 
       result[-1].append(seq[j+1]) 
     yield result 

if __name__=="__main__": 
    from pprint import pprint 
    pprint(list(composition('ABCD'))) 

Référence: https://en.wikipedia.org/wiki/Composition_(combinatorics)