找到一个和两个相加的组合

Question

我正在尝试通过加一和二来获得所有可能的组合和排列以达到一个数字。例如，您可以通过添加 1 + 1 + 2 或 2 + 2 + 1 等来获得 5
objective:return 由 1 和 2 组成的所有列表的列表，其中元素的总和等于参数
正如指出的那样，我的代码不适用于 0、1 和 2
例如：

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

我已经找到了一种方法，但它只能工作到 7，因为它找不到 'middle' 组合（不是最多的 1 或两个，只是平均数量）。
我的函数没有找到任何排列，它只是进行组合。

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

用法： 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

你要的是整数compositions——具体来说，就是只包含 1 和 2 的组合。

因为这个 is 是斐波那契数列，所以理所当然地，可能的解决方案在结构上类似于斐波那契算法。这是一个递归版本：

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

解释：让 F(n) = n 的所有组合仅由 1 和 2 组成。每篇作文必须以 1 或 2 开头。

如果 n 的组合以 1 开头，则它后面必须跟 n - 1 的组合。如果它以 2 开头，那么它后面必须跟 n - 2 的组合。因此，n 的所有组合要么是 1 后跟 n - 1 的所有组合，要么是 2 后跟 n - 2 的所有组合，这正是这里的递归情况 "saying".

这是一个基本的迭代版本：

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

对于迭代版本，我们从基本情况开始：a设置为0的所有组合（只有一个：空组合），b设置为1 的所有组合。在每次迭代中，a 和 b 是 "moved forward" 一步。所以在一次迭代之后，a := F(1) 和 b := F(2)，然后是 a := F(2) 和 b := F(3)，依此类推。

假设 a := F(k) 和 b := F(k + 1)。 a 的下一个值应该是 F(k + 1)，这只是 b 的当前值。要查找 b 的下一个值，请注意：

如果在 k + 1 的合成中加 1，则得到 k + 2 的合成。
如果你在 k 的合成中加上 2，那么你也会得到 k + 2 的合成。
事实上，这些是构成 k + 2 的唯一方法，因为我们只能使用 1 和 2。

因此，b 的新值 F(k + 2) 是 1 加上所有旧值 b (F(k + 1)) 和 2 加上所有a (F(k)).

的旧值

重复 n 次，最后得到 a := F(n) 和 b := F(n + 1)。

但是请注意，由于结果的长度等于 Fibonacci(n+1)，因此以上两个功能都很快无法使用。

Answer 2

不需要一些复杂的代码来做到这一点。

我的函数：

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

Answer 3

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

用法：
print(findCombos(7))
输出：
[[(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)]

找到一个和两个相加的组合

Find combinations of one and two that add to a number

math

combinations

permutation

python-3.x