Alle möglichen Kombinationen in einer dynamischen Reihenfolge versuchen

Question

Grundsätzlich bin ich auf der Suche nach einer Implementierung von itertools.product, die mir erlaubt, die Reihenfolge, in der die Kombinationen generiert werden, zu ändern.

Beispiel: Wenn ich itertools.product('AB', 'xy') erzeugt es die Kombinationen in genau dieser Reihenfolge:

[('A', 'x'), ('A', 'y'), ('B', 'x'), ('B', 'y')] 

Ich brauche eine Implementierung, die wie folgt auf Anfragen wie „Bitte ändern A nach B next“, zum Beispiel antwortet:

>>> generator = DynamicOrderProduct({'var1': 'AB', 'var2': 'xy'}) 
>>> generator.first() 
{'var1': 'A', 'var2': 'x'} 
>>> generator.change('var1') 
{'var1': 'B', 'var2': 'x'} 
>>> generator.change('var2') 
{'var1': 'B', 'var2':, 'y'} 
>>> generator.change('var2') # here it can't generate a new combination by 
          # changing var2, so it changes var1 instead 
{'var1': 'A', 'var2': 'y'} 
>>> generator.change('var2') 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
StopIteration 

---

Idealerweise würde der Generator eine Liste von Variablen wie folgt akzeptieren:

generator.change(['var1', 'var2']) 

Es sollte dann versuchen, den Wert von var1 zu ändern, und wenn das nicht möglich ist, ändern Sie stattdessen den Wert var2 und so weiter.

---

Wie würde ich das umsetzen? Gibt es etwas in der Standardbibliothek, die mir helfen kann?

Answer 1

In Ordnung, ich habe es geschafft, einen Iterator zu schreiben, der das macht, was ich will. Es ist das hässlichste Stück Code, das ich je geschrieben habe, aber es macht den Job erledigt.

Ich hoffe immer noch auf eine bessere Lösung - diese Implementierung behält eine Reihe aller zurückgegebenen Kombinationen, die wachsen können, um ziemlich viel Speicher zu verwenden.

class DynamicOrderProduct: 
    """ 
    Given a dict of {variable: [value1,value2,value3,...]}, allows iterating 
     over the cartesian product of all variable values. 
    Each step in the iteration returns a mapping of {variable: value}. 
    To start the iteration, retrieve the first mapping by calling .first(). 
    To retrieve subsequent mappings, call 
     .next(order_in_which_to_change_variable_values). This function's 
     parameter should be a list of variables sorted by which variable's value 
     should change next. If possible, the first variable in the list will 
     change value. If not, the 2nd variable in the list will change value 
     instead, and so on. Raises StopIteration if all combinations are 
     exhausted. 

    Example: 

     possible_values = {'B': [0,1], # B can take the value 0 or the value 1 
          'L': [1,2,3]} 
     iterator = DynamicOrderProduct(possible_values) 
     print(iterator.first()) 

     import random 
     variables = list(possible_values.keys()) 
     while True: 
      order = random.sample(variables, len(variables)) 
      print('advancing variables in this order:', order) 
      try: 
       print(iterator.next(order)) 
      except StopIteration: 
       break 

    You may also pass an incomplete list of variables to the .next function. 
    If no new combination of the given variables is possible, StopIteration is 
     raised. For example: 

     iterator = DynamicOrderProduct({var1: [1], 
             var2: [1,2]}) 
     iterator.first() # this returns {var1: 1, var2: 1} 
     iterator.next([var1]) # raises StopIteration 

    Also, you may pass multiple lists to .next in order to change the value of 
     multiple variables. StopIteration will be raised only if no variable can 
     change value. 

     iterator = DynamicOrderProduct({var1: [1,2], 
             var2: [1,2]}) 
     iterator.first() # this returns {var1: 1, var2: 1} 
     iterator.next([var1], [var2]) # returns {var1: 2, var2: 2} 
    """ 
    def __init__(self, possible_variable_values): 
     self.possible_variable_values = {k:tuple(v) for k,v in \ 
             possible_variable_values.items()} 
     self.variable_order = list(possible_variable_values) 
     self.exhausted_combinations = set() 

    def first(self): 
     self.mapping = {var:vals[0] for var,vals in \ 
         self.possible_variable_values.items()} 
     t = tuple(self.mapping[var] for var in self.variable_order) 
     self.exhausted_combinations.add(t) 
     return self.mapping 

    def next(self, *orders): 
     def advance(order, index, maxindex=2147483648): 
      while True: # loop to reduce recursion 
       try: 
        variable = order[index] 
       except IndexError: 
        raise StopIteration 

       value = self.mapping[variable] 
       valindex = self.possible_variable_values[variable].index(value) 
       start_index = valindex 
       while True: # change the value until we find a new combination 
        valindex += 1 
        try: 
         possible_values = self.possible_variable_values 
         value = possible_values[variable][valindex] 
        except IndexError: 
         valindex = 0 
         value = self.possible_variable_values[variable][0] 
        self.mapping[variable] = value 

        # if we've tried all values but none of them 
        # worked, try to change the next variable's 
        # value instead 
        if valindex == start_index: 
         if index+1 >= maxindex: 
          raise StopIteration 
         # instead of recursing, update our own parameters and 
         # start a new iteration 
         index += 1 
         break 

        t = tuple(self.mapping[var] for var in self.variable_order) 
        # if this combination isn't new, try 
        # changing the previous variables' values 
        if t in self.exhausted_combinations: 
         if index == 0: 
          continue 
         try: 
          return advance(order, 0, index) 
         except StopIteration: 
          continue 
        return t 

     total_order = [] 
     fail = True 
     for order in orders: 
      # each iteration may also change the previous 
      # iterations' variables 
      total_order = order + total_order 
      try: 
       t = advance(total_order, 0) 
      except StopIteration: 
       fail = True 
      else: 
       fail = False 
     if fail: 
      raise StopIteration 

     self.exhausted_combinations.add(t) 
     return self.mapping