Попытка всех возможных комбинаций в динамическом порядке

Question

В основном я ищу реализацию itertools.product, которая позволяет мне изменить порядок создания комбинаций.

Пример: Если я использую itertools.product('AB', 'xy') он генерирует комбинации в указанном порядке:

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

мне нужна реализация, которая отвечает на запросы, как «Пожалуйста, измените А до В следующий», например, как это:

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

---

в идеале, генератор будет принимать список переменных, как это:

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

Затем следует попытаться изменить значение var1, и если это невозможно, вместо этого измените значение var2 и т. Д.

---

Как я могу реализовать это? Есть ли что-то в стандартной библиотеке, которая может мне помочь?

Answer 1

Хорошо, мне удалось написать итератор, который делает то, что я хочу. Это самый уродливый фрагмент кода, который я когда-либо писал, но он выполняет свою работу.

Я все еще надеюсь на лучшее решение, хотя - эта реализация сохраняет набор всех возвращенных комбинаций, которые могут вырасти, чтобы использовать довольно много памяти.

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