Find combinations of one and two that add to a number

Question

I am trying to get every possible combination and permutation of adding one and two to reach a number. For example, you can get to 5 by adding 1 + 1 + 2 or 2 + 2 + 1, etc.
objective:return a list of all lists made of 1's and 2's where the sum of the elements equals the parameter
my code won't work for 0,1, and 2 as pointed out
for example:

3: [1,1,1],[1,2],[2,1] 
4: [1,1,1,1],[1,2,1],[2,1,1],[1,1,2],[2,2] 

I have figured out a way of doing it, but it only works up till 7, as it won't find the 'middle' combination (not the most 1's or two's, just an average amount).
My function doesn't find any permutations, it just does the combinations.

def findsum(x):
    numbers = []
    numOfOnes= x - 2
    numbers.append([1]*x) # all ones
    numbers.append([1] * numOfOnes + [2]) #all ones and a two
    if x % 2 == 0:
        numOfTwos = int((x - 2)/2)
        numbers.append([2]*(int(x/2))) # all twos
        if x >= 6:
            numbers.append([2] * numOfTwos+ [1,1]) #all twos and 2 ones

    else:
        numOfTwos = int((x - 1)/2)
        numbers.append([2] * numOfTwos+ [1])

    return numbers  

Usage: print(findsum(6))

# if number is greater that 7, won't get middle combination. Ex:
# [1,1,1,2,2] = 7 #doesn't have max 1's or 2's, , so won't be found in my algo
# [1,1,2,2,1,1] = 8 #doesn't have max 1's or 2's, so won't be found in my algo.

Answer 1

What you're after are called integer compositions--specifically, compositions that only include 1 and 2.

Because this problem is related to the Fibonacci sequence, it stands to reason that a possible solution would be structurally similar to a Fibonacci algorithm. Here's a recursive version:

def f_rec(n):
    assert n >= 0

    if n == 0:
        return [[]]
    elif n == 1:
        return [[1]]
    else:
        return [[1] + composition for composition in f_rec(n - 1)] \
             + [[2] + composition for composition in f_rec(n - 2)]

Explanation: let F(n) = all the compositions of n consisting of only 1's and 2's. Every composition must begin with a 1 or 2.

If a composition of n begins with a 1, then it must be followed by a composition of n - 1. If it begins with a 2, then it must be followed by a composition of n - 2. Hence, all the compositions of n are either 1 followed by all the compositions of n - 1, or 2 followed by all the compositions of n - 2, which is exactly what the recursive case here is "saying".

---

Here's a basic iterative version:

def f_iter(n):
    assert n >= 0

    a, b = [[]], [[1]]

    for _ in range(n):
        a, b = b, [[1] + c for c in b] + [[2] + c for c in a]

    return a

For the iterative version, we start from the base cases: a is set to all the compositions of 0 (there is exactly one: the empty composition), and b is set to all the compositions of 1. On each iteration, a and b are "moved forward" by one step. So after one iteration, a := F(1) and b := F(2), then a := F(2) and b := F(3), and so on.

Suppose a := F(k) and b := F(k + 1). The next value of a should be F(k + 1), which is simply the current value of b. To find the next value of b, note that:

• if you add a 1 to a composition of k + 1, then you get a composition of k + 2.
• if you add a 2 to a composition of k, then you get a composition of k + 2 as well.
• in fact, these are the only ways to form a composition of k + 2, since we can only use 1's and 2's.

Thus, the new value of b, which is F(k + 2), is 1 plus all of the old value of b (F(k + 1)) and 2 plus all of the old value of a (F(k)).

Repeat this n times, and you end up with a := F(n) and b := F(n + 1).

---

Note, however, that because the length of the result is equal to Fibonacci(n+1), both functions above because unusable very quickly.

Answer 2

import math
import itertools
def findCombos(n):
    max2s = math.floor(n/2)

    min1s = n - max2s

    sets = []
    #each set includes [numOfTwos,numOfOnes]
    for x in range(max2s+1):
        sets.append([x,n-(x*2)])
    #creates sets of numberOfOnes and numberOfTwos
    numsets = []
    allsets = []
    for x in sets:
        numsets.append(x[0] * [2] + x[1] * [1])
    #changes set to number form , [2,3] >> [2,2,1,1,1]
    for eachset in numsets:
        if 1 in eachset and 2 in eachset:
            #if can be permutated(has 2 different numbers)
            y = set(itertools.permutations(eachset))
            #y is all the permutations for that set of numbers
            for z in y:
                #for each tuple in the list of tuples, append it
                allsets.append(z)
        else:
            #otherwise just append the list as a tuple
            allsets.append(tuple(eachset))
    return allsets

Usage:
print(findCombos(7))
Output:
[[(1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 2), (1, 2, 1, 1, 1, 1), (1, 1, 1, 2, 1, 1), (1, 1, 2, 1, 1, 1), (2, 1, 1, 1, 1, 1), (1, 1, 1, 1, 2, 1), (1, 2, 1, 1, 2), (2, 1, 1, 1, 2), (2, 1, 2, 1, 1), (2, 1, 1, 2, 1), (1, 1, 2, 1, 2), (1, 1, 1, 2, 2), (1, 2, 2, 1, 1), (1, 2, 1, 2, 1), (1, 1, 2, 2, 1), (2, 2, 1, 1, 1), (2, 2, 1, 2), (2, 1, 2, 2), (2, 2, 2, 1), (1, 2, 2, 2)]

Answer 3

No needs some complex code to do that.

My function :

def findsum(x) :
    base = [1]*x

    i = 0
    baseMax = ''
    while i < x :
        try :
            baseMax += str(base[i] + base[i+1])
        except IndexError :
            baseMax += str(base[i])
        i += 2

    baseList = []
    for i, n in enumerate(baseMax) :
        if n == '2' :
            baseList.append(baseMax[:i].replace('2', '11') + '1'*2 + baseMax[i+1:])
    baseList.append(baseMax)

    from itertools import permutations
    results = set()
    for n in baseList :
        if n.count('1') and n.count('2') :
            for p in sorted(permutations(n, len(n))) :
                results.add(''.join(list(p)))
        else :
            results.add(n)
    return sorted(results, key=int)

print(findsum(7))
# ['1222', '2122', '2212', '2221', '11122',
# '11212', '11221', '12112', '12121', '12211',
# '21112', '21121', '21211', '22111', '111112',
# '111121', '111211', '112111', '121111', '211111',
# '1111111']