sum（xi）= b、線形制約付きのすべての整数解を見つける方法

Question

sum（xi）= 10、0 < = xi < = 2、i = 1,2、...、10.とするとxiのすべての整数解を求める。ありがとうございました。私はEuclideanアルゴリズムについて読んだことがありますが、2つの未知の変数のように見えます。ここではどのようなアルゴリズムを使用できますか？

Answer 1

再帰が最適です。あなたが最初にメモリに長いリストを作成する必要はありませんということで発電機の

def solutions(variables, sum_left, max_value): 
    if 0 == variables: 
     if 0 == sum_left: 
      yield [] 
    else: 
     for i in range(0, max_value + 1): 
      if sum_left < i: 
       break 
      else: 
       for partial_solution in solutions(variables - 1, sum_left - i, 
                max_value): 
        yield [i] + partial_solution 

for x in solutions(10, 10, 2): 
    print(x) 

利益：ここでは発電機との自然なPythonのソリューションです。ここでは、発電機を使用せず、リストを構築することを避ける別の解決法があります。

def do_something_for_solutions(variables, sum_left, max_value, known=None): 
    if known is None: 
     known = [] 
    if 0 == variables: 
     if 0 == sum_left: 
      do_something(known) 
    else: 
     for i in range(0, max_value + 1): 
      if sum_left < i: 
       break 
      else: 
       do_something_for_solutions(variables - 1, sum_left - i, 
              max_value, known + [i]) 

def do_something(solution): 
    print(solution) 

do_something_for_solutions(10, 10, 2) 

あなたが解決策を返却することを選択した場合、次のように、それが可能である：

def solutions(variables, sum_left, max_value): 
    if 0 == variables: 
     if 0 == sum_left: 
      return [[]] 
     else: 
      return [] 
    else: 
     answer = [] 
     for i in range(0, max_value + 1): 
      if sum_left < i: 
       break 
      else: 
       for partial_solution in solutions(variables - 1, sum_left - i, 
                max_value): 
        answer.append([i] + partial_solution) 
     return answer 

for x in solutions(10, 10, 2): 
    print(x) 

（あなたはパラメータを変更した場合、そのリストは簡単に巨大になることができると警告したことが...）

Answer 2

は、各整数パーティションは最大10重量部で

• を有し番号100、のinteger partitionsの順列を探しています。そして
• 各部分は、最大で15

例多くは確かにありますが、10です！それらはコンピュータによってまだ管理可能です。

編集：OPはそう、質問を編集した：あなたは本当にすべてのソリューションを持っているしたい場合は番号10は、各部分が、せいぜい2

Answer 3

で高々10部、との整数のパーティションに分割する必要があります：再帰的にいくつかの最適化と可能なすべての変数の割り当てを列挙：

1. 最後の変数の値は、部分的な割り当てがもはや導くことができないことを見たときに検索が、剪定することができ、和制約
2. から計算することができます有効な解に変換する（例えば、合計が既に大きい場合n 10または10の合計に到達する変数が少なすぎる場合）