Итерации через комбинации сумм в Python 3

Я ищу способ найти все комбинации сумм с элементами последовательности Фибоначчи с заданным пределом, который равен тому же значению. Я знаю, что combinations() от itertools - наша лучшая ставка для решения таких проблем, но поскольку я новичок в Python, мне нравится знать, как я могу сохранить совпадающие комбинации (поскольку только один правильный, поскольку это не конец алгоритма).Итерации через комбинации сумм в Python 3

я в настоящее время:

# Call Fibonacci sequence with a given limit: 
def fib1(n): 
    result = [] 
    a, b = 1, 1 
    while a < n: 
     result.append(a) 
     a, b = b, a + b 
    return result 


# Wrong code, skeleton: 
def zeckendorf(n): 
    from itertools import combinations 
    seq = fib1(n) 
    row = [] 
    sum = 0 
    for i in combinations(seq, len(seq)): 
     sum += i 
     row.append(i) 
     if sum > n: 
      sum = 0 
      row = [] 
      continue 
     elif sum == n: 
      break 

    return row

Теперь я знаю, что второй бит неправильно во многих отношениях. Кроме того, я делаю ошибку, чтобы попытаться добавить кортежи в целые числа. Мне просто нужно знать, как я могу перебирать отдельные элементы этих комбинаций отдельно, используя модуль itertools. Полезны только комбинации с суммой «n».

источник

2013-03-29 Denny Nuyts

Я думаю, что вы ищете функцию 'itertools.permutations', b ecause 'сочетания (seq, len (seq))' имеет только 1 элемент, сам 'seq'. От doc до 'комбинаций': * Возвращает r подпоследовательности элементов из входного итерабельного. * Существует только 1 подпоследовательность с длиной всей последовательности, и это сама последовательность. – halex

Я уверен, что ищу комбинации. Поскольку не все элементы должны использоваться. Каждое целое число может быть выражено как сумма чисел Фибоначчи по значению целого числа. И эти числа Фибоначчи могут использоваться только один раз. –

Во всяком случае, мой код не имеет смысла, и я знаю об этом. Моя основная проблема заключается в том, чтобы узнать, как работает модуль itertools. Я также думаю, что это сложно проверить в оболочках Python, это одно. Например, –

Если я правильно то, что вы пытаетесь достичь, то используйте следующий код: понять

def zeckendorf(n): 
    seq = fib1(n) 
    for i in range(1, len(seq)): 
     for comb in itertools.combinations(seq, i): 
      if sum(comb) == n: 
       return list(comb) 
    return []

Если вам нужно дополнительное объяснение этого кода просто спросить :)

источник

2013-03-29 11:10:26 halex

Это на самом деле помогает мне. Спасибо. Просто нужно добавить некоторые детали, и я готов идти. Если бы я только знал о чем-то простом, как встроенная функция 'sum()'. ;) –

Чтобы найти все комбинации с нужной суммой, добавьте каждую комбинацию в список результатов:

def combinations_with_sum(sequence, desired_sum): 
    results = [] 
    for i in range(len(sequence)): 
     results.extend([combination for combination in combinations(sequence, i) 
         if sum(combination) == desired_sum]) 
    return results

источник

2013-03-29 11:13:27 Adam

Спасибо. Задача решена. Просто нужно сделать одну крошечную вещь (убедитесь, что элементы не следуют друг за другом в последовательности Фибоначчи), но это не проблема. Кажется, все, что мне нужно было знать, это использовать функцию 'sum()'. –

Итерации через комбинации сумм в Python 3

ответ

Смежные вопросы