Permutations imbriquées à partir du modèle

Question

J'écris un programme qui prend un permutations de «modèle» de chaînes, et affiche toutes les permutations en fonction de ce modèle. Le modèle ressemble à ceci:

model = Mix([ 
    [ 
     "this", 
     PickOne(["is", "isn't"]) 
    ], 
    PickOne([ 
     Mix([ 
      "absolutely", 
      "great" 
     ]) 
    ]) 
]) 

Dans les permutations en sortie,

1. list objets affichera les objets contenant dans l'ordre
2. Mix objets affichera les dans tous les ordres possibles objets contenant avec toujours longueur maximale possible (y compris zéro)
3. PickOne objets ne produiront qu'un seul de ses objets à la fois

Ainsi, la sortie désirée de l'exemple ci-dessus serait:

[ 
    ["this", "is"], 
    ["this", "isn't"], 
    ["this", "is", "absolutely"], 
    ["this", "is", "great"], 
    ["this", "isn't", "absolutely"], 
    ["this", "isn't", "great"], 
    ["absolutely"], 
    ["great"], 
    ["absolutely", "this", "is"], 
    ["great", "this", "is"], 
    ["absolutely", "this", "isn't"], 
    ["great", "this", "isn't"], 
    [] 
] 

Jusqu'à présent, je l'ai mis en œuvre les permutations pour la classe Mix comme ceci:

class Mix(list): 
    def __init__(self, *args, **kwargs): 
     super(Mix, self).__init__(*args, **kwargs) 
     self.permutations = [] 
     for L in range(0, len(self)+1): 
      for subset in itertools.combinations(self, L): 
       subset_permutations = itertools.permutations(subset) 
       self.permutations.extend(subset_permutations) 

et mon PickOne classe est simplement cela

class PickOne(list): 
    pass 

que je suis le plan en testant simplement dans ma fonction principale et en la manipulant en conséquence (if type(obj) is PickOne: ...).

itertoolsitertools offre simplification et efficacité pour des cas d'utilisation plus simples, mais je ne sais pas comment cela va m'aider pour cette implémentation (au-delà de ce que j'ai déjà implémenté dans Mix). Des idées de la façon dont itertools peut être utilisé pour aider à une mise en œuvre Pythonic de ce qui précède?

Answer 1

J'ai quelques problèmes à faire tourner ma tête autour de toutes ces combinaisons, mais je pense que votre classe Mix doit également donner le product de tous ceux permutations. J'ai créé un modèle similaire pour le tester. Cela pourrait fonctionner un peu différent que le vôtre, mais il devrait être facile à adapter:

class CombModel: 
    def __init__(self, *options): 
     self.options = options 

class Atom(CombModel): 
    def __iter__(self): 
     for x in self.options: 
      yield x 

class All(CombModel): 
    def __iter__(self): 
     for prod in itertools.product(*self.options): 
      yield prod 

class One(CombModel): 
    def __iter__(self): 
     for x in self.options: 
      for y in x: 
       yield y 

class Mix(CombModel): 
    def __iter__(self): 
     for n in range(len(self.options) + 1): 
      for perm in itertools.permutations(self.options, n): 
       for prod in itertools.product(*perm): 
        yield prod 

Le CombModel ne fournit qu'un constructeur var-arg pour tous les sous-classes. Atom est une "feuille" dans le modèle et il est là pour que je puisse "itérer" même sur des chaînes simples ou entiers. Cela économise une logique if/else dans toutes les autres classes. All est ce qui semble être des listes simples dans votre modèle, ce qui donne le produit des différentes options. One et Mix correspondent à vos PickOne et Mix.

En utilisant ce modèle assez simple comb = Mix(All(Atom(1), Atom(21, 22)), One(Atom(31, 32), Atom(4))) je reçois les ces combinaisons:

() 
((1, 21),) 
((1, 22),) 
(31,) 
(32,) 
(4,) 
((1, 21), 31) 
((1, 21), 32) 
((1, 21), 4) 
((1, 22), 31) 
((1, 22), 32) 
((1, 22), 4) 
(31, (1, 21)) 
(31, (1, 22)) 
(32, (1, 21)) 
(32, (1, 22)) 
(4, (1, 21)) 
(4, (1, 22)) 

Votre modèle se traduit par ceci:

model = Mix(
    All(
     Atom("this"), 
     One(Atom("is"), Atom("isn't")) 
    ), 
    One(
     Mix(
      Atom("absolutely"), 
      Atom("great") 
     ) 
    ) 
) 

Et donne ces combinaisons:

() 
(('this', 'is'),) 
(('this', "isn't"),) 
((),) 
(('absolutely',),) 
(('great',),) 
(('absolutely', 'great'),) 
(('great', 'absolutely'),) 
(('this', 'is'),()) 
(('this', 'is'), ('absolutely',)) 
(('this', 'is'), ('great',)) 
(('this', 'is'), ('absolutely', 'great')) 
(('this', 'is'), ('great', 'absolutely')) 
(('this', "isn't"),()) 
(('this', "isn't"), ('absolutely',)) 
(('this', "isn't"), ('great',)) 
(('this', "isn't"), ('absolutely', 'great')) 
(('this', "isn't"), ('great', 'absolutely')) 
((), ('this', 'is')) 
((), ('this', "isn't")) 
(('absolutely',), ('this', 'is')) 
(('absolutely',), ('this', "isn't")) 
(('great',), ('this', 'is')) 
(('great',), ('this', "isn't")) 
(('absolutely', 'great'), ('this', 'is')) 
(('absolutely', 'great'), ('this', "isn't")) 
(('great', 'absolutely'), ('this', 'is')) 
(('great', 'absolutely'), ('this', "isn't")) 

Notez que ce sont toujours des listes imbriquées (ou tuples, en fait), mais celles-ci peuvent facilement être flattened après. En outre, il existe quelques pseudo-doublons (qui seraient des doublons en cas d'aplatissement) en raison de la nature «zéro ou plus» de Mix. Mais en dehors de cela, cela semble plutôt proche de votre sortie attendue.

---

En y regardant de plus près, il pourrait en effet être necesary pour aplatir d'abord, de sorte que PickOne choisira un seul du mélange et non l'ensemble du mix ...

class All(CombModel): 
    def __iter__(self): 
     for prod in itertools.product(*self.options): 
      yield flat(prod) # flatten here 

class One(CombModel): 
    def __iter__(self): 
     for x in self.options: 
      for y in flat(x): # flatten here 
       yield y 

class Mix(CombModel): 
    def __iter__(self): 
     for n in range(len(self.options) + 1): 
      for perm in itertools.permutations(self.options, n): 
       for prod in itertools.product(*perm): 
        yield flat(prod) # flatten here 

Après le sarclage les doublons , le résultat est le suivant:

() 
('absolutely',) 
('absolutely', 'this', 'is') 
('absolutely', 'this', "isn't") 
('great',) 
('great', 'this', 'is') 
('great', 'this', "isn't") 
('this', 'is') 
('this', 'is', 'absolutely') 
('this', 'is', 'great') 
('this', "isn't") 
('this', "isn't", 'absolutely') 
('this', "isn't", 'great')