Комбинации ограниченного набора целых чисел

Question

Как сгенерировать список комбинаций с allowed_ints, который составляет goal?

Примеры:

allowed_ints=[1,2], goal=4 
combinations = [[1,1,1,1],[1,1,2],[2,1,1],[2,2],[1,2,1]] 

allowed_ints=[5, 6], goal=13 
combinations = [] 

Что я сделал до сих пор сделать не работает.

def combinations(allowed_ints, goal): 
    if goal > 0: 
     for i in allowed_ints: 
      for p in combinations(allowed_ints, goal-i): 
       yield [i] + p 
    else: 
     yield [] 

print list(combinations([1, 2],3)) 
[[1, 1, 1], [1, 1, 2], [1, 2], [2, 1], [2, 2]] # not what I want 

Answer 1

Использование вы действуете попробовать это:

def combinations(allowed_ints, goal): 
    if goal > 0: 
     for i in allowed_ints: 
      for p in combinations(allowed_ints, goal-i): 
       if sum([i] + p) == goal: 
        yield [i] + p 
    else: 
     yield [] 

print list(combinations([1, 2],3)) 

Выходы:

[[1, 1, 1], [1, 2], [2, 1]] 

Answer 2

Вы должны включать 3 условия, такие как

цель == 0, то рекурсия работал

< цель 0, то рекурсия потерпел неудачу

цель положить конец> = 0 и элементы списка, то рекурсия не удалось

Кстати, вы можете сделать все это с помощью рекурсии. Нет необходимости в цикле, рекурсия может также сделать петлю

Answer 3

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

def combinations(allowed_ints, list, goal): 
    # base case: you're done 
    if sum(list) == goal: 
     print list 
    # if overshoot, stop here 
    elif sum(list) > goal: 
     pass 
    else: 
     for i in allowed_ints: 
      new_list = list[:] 
      new_list.append(i) 
      combinations(allowed_ints, new_list, goal) 

combinations([1, 2],[],4) 

Это не лучше, чем предложенный ответ, но использует другой подход.