Вычислить перестановки

Question

Я кортеж скажу:

my_tuple = ((1,2), 10) 

и словарь:

diction = {1:(1,2,3,4,5,6,7,8,9), 2:(1,2,3,4,5,6,7,8,9), 3:(1,2,3,4,5,6,7,8,9)} 

Первый элемент кортеж представляет некоторые переменные, которые каждый из них может быть назначен со значением 1, ..., 9 (согласно словарю).

Как вычислить все перестановки (без повторения) для этих переменных. Единственное ограничение у меня есть, что я хочу, значения моих переменных, чтобы иметь сумму 10

Например:

(var1) = 9 
(var2) = 1 

So (9,1) имеет сумму 10 и является допустимая перестановка.

Что я попытался это:

lst = [] 

first_var = my_tuple[0][0] 
sec_var = my_tuple[0][1] 

for i in diction[first_var]: 
    for j in diction[sec_var]: 
     if i != j: 
      if (i + j) == my_tuple[1]: 
       lst.append((i,j)) 

Моя проблема заключается в том, что кортеж с переменными имеет не всегда один и тот же размер (2 в данном случае). Он может содержать 3 или 4 переменных, поэтому цикл выше не работает.

Есть ли способ, которым я могу вычислить перестановки для более общего случая? Например, ((1,2,3), 20)?

Answer 1

Используйте итераторы:

def solve(d, target, total, keys, avoid): 
    if total <= target:  # omit this check if values can be negative 
    if keys: 
     k = keys[0] 
     for v in d[k]: 
     if not (v in avoid): 
      for s in solve(d, target, total+v, keys[1:], avoid.union([v])): 
      yield s + [(k,v)] 
    elif target == total: 
     yield [] 

def test1(): 
    d = {'a':(1,2,3), 'b':(4,5), 'c':(1,3,5) } 
    for s in solve(d, 10, 0, "abc", set([])): 
    print s 

def test2(): 
    d = {'a':(1,2,3), 'b':(1,2,3), 'c':(1,2,3) } 
    for s in solve(d, 6, 0, "abc", set([])): 
    print s 

Выход из test1:

[('c', 5), ('b', 4), ('a', 1)] 
[('c', 3), ('b', 5), ('a', 2)] 

Выход из test2:

[('c', 3), ('b', 2), ('a', 1)] 
[('c', 2), ('b', 3), ('a', 1)] 
[('c', 3), ('b', 1), ('a', 2)] 
[('c', 1), ('b', 3), ('a', 2)] 
[('c', 2), ('b', 1), ('a', 3)] 
[('c', 1), ('b', 2), ('a', 3)]