0

I'm look for a way to find all combinations of sums with elements of a Fibonacci sequence with a given limit which equal that same value. I know that combinations() from itertools is our best bet in solving such problems, but as I'm new in Python I like to know how I can retain the matching combinations (as only one is correct, as this is not the end of the algorithm).

I currently have:

 # 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

Now I know the second bit is wrong in many ways. Also, I make the mistake as to try to add tuples to integers. I just need to know how I can iterate through separate elements of those combinations separately using the itertools module. Only the combinations with sum 'n' are useful to me.

Improve this question
4
  • I think you are looking for the itertools.permutations function, because combinations(seq, len(seq)) has only 1 element, the seq itself. From the doc to combinations: Return r length subsequences of elements from the input iterable. There is only 1 subsequence with the length of the whole sequence and that is the sequence itself. Commented Mar 29, 2013 at 10:54
  • I'm positive I'm looking for combinations. As not all elements have to be used. Every integer can be expressed as the sum of Fibonacci numbers under the value of the integer. And those Fibonacci numbers can be only used once as well. Commented Mar 29, 2013 at 10:58
  • Anyway, my code makes little sense and I'm aware of that. My main problem still is to find out how the itertools module works. I also think it's hard to test in Python shells, this one. Commented Mar 29, 2013 at 11:00
  • For instance. The Fibonacci sequence until 100 is [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89] (0 excluded, as it's a neutral element in a sum anyway). 100 can be expressed as 3 + 8 + 89 or as 1 + 2 + 8 + 89 or as 3 + 8 + 34 + 55. Finding out how to get to those values/combinations is where I struggle with. Commented Mar 29, 2013 at 11:06

3 Answers 3

Reset to default
1

If I understand correctly what you are trying to achieve then use the following code:

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

If you need further explanation on this code just ask :)

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This actually helps me out a great bit. Thank you. Just need to add some details and I'm good to go. If only I knew about something as simple as the built-in sum() function. ;)
1

To find all the combinations with the desired sum, append each combination to a result list:

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
Improve this answer

1 Comment

Thanks. Problem solved. Just need to do one tiny thing (make sure the elements don't follow one another in the Fibonacci sequence), but that's a no-brainer. Seems all I needed to know was to use the sum() function.
0

Let's say you want to find all subsets of your input with sum < max_sum and the number of elements between min_terms and max_terms.

Here is a couple of ways to do it, I'm including the whole script to make it easier to test and play around with but basically you only need *LimitedSums() functions to get the answer.

Brute-force approach is to iterate through all subsets and check the sum and the number of elements for each subset. That's effectively what SlowLimitedSums() does - although it takes advantage of itertools.combinations() to iterate through subsets and doesn't consider subsets with more than max_terms elements.

Potentially more efficient approach is to only consider the subsets which sum up to less than max_sum. If you are building subsets recursively you can simply stop recursion as soon as the sum of your current subset exceeds max_sum, assuming all your input numbers are non-negative, or the number of elements exceeds max_terms. This is implemented in FasterLimitedSums().

Note that in the worst case your result will contain all 2^len(v) subsets - in this case there should be no significant running time difference between the two versions of *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()
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.