0

我正在寻找一种方法来查找总和与斐波那契数列元素的所有组合，其中给定的限制等于相同的值。我知道combinations()fromitertools是我们解决此类问题的最佳选择，但由于我是 Python 新手，我想知道如何保留匹配组合（因为只有一个是正确的，因为这不是算法的结束）。

我目前有：

 # 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 模块分别遍历这些组合的单独元素。只有 sum 'n' 的组合对我有用。

4

3 回答 3

1

要查找具有所需总和的所有组合，请将每个组合附加到结果列表中：

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-29T11:13:27.243 回答
1

如果我正确理解您要实现的目标，请使用以下代码：

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-29T11:10:26.480 回答
0

假设您想找到输入的所有子集 sum <和之间的max_sum元素数。min_termsmax_terms

这里有几种方法，我包含了整个脚本，以便更容易测试和使用，但基本上你只需要 * LimitedSums() 函数来获得答案。

蛮力方法是遍历所有子集并检查每个子集的总和和元素数量。这就是有效的 SlowLimitedSums()- 尽管它利用itertools.combinations()迭代子集并且不考虑具有多个max_terms元素的子集。

可能更有效的方法是只考虑总和小于 的子集max_sum。如果您正在递归地构建子集，您可以在当前子集的总和超过 时立即停止递归max_sum，假设您的所有输入数字都是非负数，或者元素数超过max_terms。这是在FasterLimitedSums().

请注意，在最坏的情况下，您的结果将包含所有2^len(v)子集 - 在这种情况下，两个版本的*LimitedSums().

import itertools
import random


def SlowLimitedSums(v, max_sum, min_terms=None, max_terms=None):
  min_terms = 0 if min_terms is None else min_terms
  max_terms = len(v) if max_terms is None else max_terms
  return sorted(set(
      sum(c) for nc in range(min_terms, max_terms + 1)
      for c in itertools.combinations(v, nc)
      if sum(c) <= max_sum))


def FasterLimitedSums(v, max_sum, min_terms=None, max_terms=None):
  l = sorted(v)
  n = len(v)
  min_terms = 0 if min_terms is None else min_terms
  max_terms = n if max_terms is None else max_terms
  result = set([])

  def RecursiveSums(s, n_terms, start_pos):
    if start_pos >= n or s > max_sum or n_terms > max_terms:
      return
    if n_terms >= min_terms:
      result.add(s)
    for p in range(start_pos, n):
      RecursiveSums(s + v[p], n_terms + 1, p + 1)

  RecursiveSums(0, 0, -1)
  return sorted(result)


def main():
  mass_list = [4, 1, 8]
  mass = 10
  print(sorted(mass_list + SlowLimitedSums(mass_list, mass, min_terms=2)))
  print(sorted(mass_list + FasterLimitedSums(mass_list, mass, min_terms=2)))


if __name__ == "__main__":
  main()
于 2018-06-03T21:12:38.817 回答