番号に追加する1と2の組み合わせを見つける

Question

数字に達するために1と2を加えることのすべての可能な組み合わせと順列を得ようとしています。たとえば、あなたが1 + 1 + 2か2 + 2 + 1を、追加して5に取得することができ目的など
：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までアップ作品中位の組み合わせ（ほとんどの1または2ではなく、平均的な量）である。
私の関数はどのような順列も見つけられません。

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 

使用法：あなたは--specifically整数compositionsと呼ばれている後にしている何 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

、このproblemがにrelatedあるので、わずか1及び2

を含む組成物フィボナッチシーケンスとは、フィボナッチアルゴリズムと構造的に類似している可能性がある解を導くことになる。ここで、再帰的バージョンは次のとおり

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

説明：​​を聞かせ=のみ1と2のなるnのすべての組成物。すべてのコンポジションは1または2で始まる必要があります。

nのコンポジションが1で始まる場合は、n - 1のコンポジションが続く必要があります。 2で始まる場合は、それに続くn - 2の構成が続く必要があります。したがって、nのすべての組成は、1の後にn - 1のすべての組成、またはそれに続くn - 2のすべての組成のいずれかです。これは、再帰的な場合がここで「言っている」ものです。ここで

---

は、基本的な反復バージョンです：反復バージョンについては

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は1ステップで「前に移動」されます。だから、1回の反復の後に、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 + 2の構図を取得し、k + 1の組成物に1を追加した場合。
• kのコンポジションに2を追加すると、k + 2のコンポジションも得られます。
• 実際には、これはk + 2の構成を作成する唯一の方法です.1と2を使用できるためです。

したがって、F(k + 2)あるbの新しい値は、1であり、プラスb（F(k + 1)）と2プラスa（F(k)）の古い値のすべての古い値の全。

これを繰り返すとa := F(n)とb := F(n + 1)となります。

---

ただし、結果の長さがFibonacci(n+1)に等しいので、その、使用不可能なので、非常に迅速に上記の両方の機能を有します。

Answer 2

これを行うには、複雑なコードは必要ありません。

My機能：

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