定義済みの値で1次元空間を塗りつぶします

Question

定義済みの "subLengths"で長さを設定したいと思います。 私のsubLengthは3,4,5,6,7,10です。 長さを15桁にするには、「10 + 5」、「3 + 4 + 3 + 5」、「7 + 4 + 4」、「7 + 5 + 3」を使用できます.... これらの結果の配列の1つとして？ より良い結果を得るにはどうすればよいでしょうか？私の最大の長さは70です。私は、この価値のために良い結果を得るには時間がかかるかもしれないと思います。

私は3Dのアーティストです。私のコーディングスキルは限られていますが、この問題に対処する方法がわかりません。PythonやCのような言語を使用できます。

このコードは私のソフトウェアで動作するようです：

def fillBuild(length, subLengths): 

    for i in range(len(subLengths)):   
      if subLengths[i] == length: 
        yield subLengths[i:i + 1] 
      elif subLengths[i] < length: 
        for subResult in fillBuild(length - subLengths[i] ,subLengths[i:]): 
          yield subLengths[i:i + 1] + subResult 

Answer 1

再帰ジェネレータ機能（パイソン）totalまで追加poolの（繰り返して）すべての可能なサブリストの順列を生成：

from pprint import pprint 

def sub_lists(pool, total): 
    for i in range(len(pool)): 
     if pool[i] == total: 
      yield pool[i:i + 1] 
     elif pool[i] < total: 
      for sub_list in sub_lists(pool, total - pool[i]): 
       yield pool[i:i + 1] + sub_list 

pprint(list(sub_lists([3, 4, 5, 6, 7, 10], 15))) 
[[3, 3, 3, 3, 3], 
[3, 3, 3, 6], 
[3, 3, 4, 5], 
[3, 3, 5, 4], 
[3, 3, 6, 3], 
[3, 4, 3, 5], 
[3, 4, 4, 4], 
[3, 4, 5, 3], 
[3, 5, 3, 4], 
[3, 5, 4, 3], 
[3, 5, 7], 
[3, 6, 3, 3], 
[3, 6, 6], 
[3, 7, 5], 
[4, 3, 3, 5], 
[4, 3, 4, 4], 
[4, 3, 5, 3], 
[4, 4, 3, 4], 
[4, 4, 4, 3], 
[4, 4, 7], 
[4, 5, 3, 3], 
[4, 5, 6], 
[4, 6, 5], 
[4, 7, 4], 
[5, 3, 3, 4], 
[5, 3, 4, 3], 
[5, 3, 7], 
[5, 4, 3, 3], 
[5, 4, 6], 
[5, 5, 5], 
[5, 6, 4], 
[5, 7, 3], 
[5, 10], 
[6, 3, 3, 3], 
[6, 3, 6], 
[6, 4, 5], 
[6, 5, 4], 
[6, 6, 3], 
[7, 3, 5], 
[7, 4, 4], 
[7, 5, 3], 
[10, 5]] 

Answer 2

は、ここではPython 2.7を使用して、再帰的なソリューションです：

def fill(length, sublengths): 
    # IMPORTANT: this function will produce INCORRECT RESULTS if sublengths 
    # is not a list of unique integers sorted increasingly. 

    fillings = [] 

    for i, sublength in enumerate(sublengths): 

     if sublength > length: 
      # if sublength is greater than length, there are no more allowable 
      # fillings (because sublengths are unique and are sorted 
      # increasingly), so we return the fillings collected so far; 
      return fillings 

     elif sublength == length: 
      # if sublength is exactly equal to length, then only one filling is 
      # possible, namely [sublength]; we append this filling to the 
      # fillings; 
      fillings.append([sublength]) 

     else: 
      # we generate all the fillings that begin with sublength by 
      # prepending sublength to all the allowable fillings of 
      # (length - sublength), which we obtain by making a recursive call. 
      fillings.extend([[sublength] + subresult 
          for subresult in 
          fill(length - sublength, sublengths[i:])]) 

例：

In [2]: fill(15, [3, 4, 5, 6, 7, 10]) 
Out[2]: 
[[3, 3, 3, 3, 3], 
[3, 3, 3, 6], 
[3, 3, 4, 5], 
[3, 4, 4, 4], 
[3, 5, 7], 
[3, 6, 6], 
[4, 4, 7], 
[4, 5, 6], 
[5, 5, 5], 
[5, 10]] 

ところで：fill(70, [3, 4, 5, 6, 7, 10]))は1657を生成可能な充填物なので、あなたは何か別の基準をして祖先。

---

いくつかの注意：

• ソリューションの繰り返しを避けるために、私たちは、それぞれの充填がますます注文することが必要になります。

• キーアイデアはこれです：埋めるために長さがLあり、かつ < < ... < _Nが利用可能であることを仮定sublengths。 からとを開始Lのすべての可能な詰め物を見つけるにはLのすべての詰め物にを付加することと同じです。これはelseブロックの再帰呼び出しの根拠です。fillです。 （関数が自身を呼び出すとき、fillのように、この関数はの再帰と呼ばれます。fillので）

• は、重複のないことがsublengthsを必要とますます、我々はこれらの条件を満たしていることを確認するために、次のフロントエンド機能を使用することができソート：

  DEF（長さ、sublengths）をdo_fill： 戻りフィル（長さ、ソート（セット（sublengths）））

---

（NB：以下は何タラのかなり詳細な説明でありますeはそうです。コードをすでに理解していれば、この記事の残りの部分は安全にスキップすることができます）。

先ほどの例に戻って、最初のサブ長に従ってソリューションをグループ化してください。 、今

# group I 
[3, 3, 3, 3, 3] 
[3, 3, 3, 6] 
[3, 3, 4, 5] 
[3, 4, 4, 4] 
[3, 5, 7] 
[3, 6, 6] 

# group II 
[4, 4, 7] 
[4, 5, 6] 

# group III 
[5, 5, 5] 
[5, 10] 

私はsublengthsを使用して、15-3 = 12のための詰め物で、3で始まるすべてが、グループ内の詰め物を比較する[3、4：あなたは、以下の3つのグループを取得します、5、6、7、10]：

In [3]: fill(15 - 3, [3, 4, 5, 6, 7, 10]) 
Out[3]: 
[[3, 3, 3, 3], 
[3, 3, 6], 
[3, 4, 5], 
[4, 4, 4], 
[5, 7], 
[6, 6]] 

今、あなたは、これらすべての詰め物に3を付加した場合、あなたは正確にグループIの詰め物が

今すぐグループIIに詰め物を考え得るでしょう、これらはすべて、4で始まります。サブ長[4,5,6,7,10]を使用して、15 - 4 = 11の塗りつぶしと比較します。

In [4]: fill(15 - 4, [4, 5, 6, 7, 10]) 
Out[4]: 
[4, 7], 
[5, 6] 

また、これらのすべてのフィリングに4を追加すると、グループIIのフィリングが正確に得られます。

[3,4,5,6,7,10]ではなく、上記のfillへの最後の呼び出しで[4,5,6,7,10]をサブ長として使用したのはなぜですか？これは、ますます注文が増え、4から始まるフィリングだけに興味があるからです。これは、3を含むフィリングを除外します。

最後に、グループIIIのフィリングを得るには、15 - 5 = 10、sublengths [5、6、7、10]を用いて：あなたは、サブグループの各々のための分析の同じ種類を繰り返すことができるように傾斜している場合

In [5]: fill(15 - 5, [5, 6, 7, 10]) 
Out[5]: 
[[5, 5], 
[10]] 

---

を。たとえば、fill(15 - 3, [3, 4, 5, 6, 7, 10])によって生成された塗りつぶしを、のの最初の要素に従ってグループ化することができます。で」

fill((15 - 3) - 3, [3, 4, 5, 6, 7, 10]) 
fill((15 - 3) - 4, [ 4, 5, 6, 7, 10]) 
fill((15 - 3) - 5, [  5, 6, 7, 10]) 
fill((15 - 3) - 6, [   6, 7, 10]) 

ちょうど上記の分析が行うことにより、生産フィリングに、それぞれ3、4、5、または6を、付加することで

[3, 3, 3, 3] 
[3, 3, 6] 
[3, 4, 5] 

[4, 4, 4] 

[5, 7] 

[6, 6] 

これらのグループ

が得られる：あなたは4つのグループを取得したいです正確に何をfill関数が "手"を行います。

注意すべき重要な点は、すべての再帰呼び出しで問題がより簡単になることです。例えば

、fill次の呼び出しが行わ得た[7、5、3]充填生成する過程において：

fill(15,   [3, 4, 5, 6, 7, 10]) = fill(15, [3, 4, 5, 6, 7, 10]) 
fill(15 - 3,  [3, 4, 5, 6, 7, 10]) = fill(12, [3, 4, 5, 6, 7, 10]) 
fill(15 - 3 - 5, [  5, 6, 7, 10]) = fill(7, [  5, 6, 7, 10]) 

注特に最後のもの、fill(7, [5, 6, 7, 10])。その解決策を点検することができます：副長さ[5,6,7,10]から7の充填が1回だけ可能です。再帰は、これらの簡単な場合の解で終わります。究極の解決策は、これらの些細なものから組み立てられます。