用预定义值填充一维空间

Question

我想用预定义的“子长度”填充长度。 假设我的子长度是：3，4，5，6，7，10。 我可以用“10+5”，“3+4+3+5”，“7+4+4”，“7+5+3”。。。。 作为一个数组，我如何得到这些结果之一？ 更好：如何获得一个数组来获得几个好的结果？我的最大长度是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

递归生成器函数（Python），生成所有可能的子列表置换（带重复）的pool加起来total：

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，而a₁<；a₂<。。。<；a_n是可用的子长度。找到以a₁开始的L的所有可能填充，等于将a₁的所有填充预先添加到L-a₁。这就是fill的else块中递归调用的基本原理。（当函数调用自身时，如fill所做的，该函数被称为递归的）

• 由于fill要求sublengths没有重复项，并且排序越来越多，我们可以使用以下前端函数来确保满足这些条件：

  def DOU fill（长度、子长度）： 返回填充（长度，排序（设置（子长度）））

---

（注意：下面是对代码作用的相当详细的解释。如果您已经理解了代码，您可以放心地跳过本文的其余部分。）

为了更好地了解发生了什么，请返回到上面的示例，并根据第一个子长度对解决方案进行分组；您将得到如下所示的三个组：

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

现在，使用子长度[3，4，5，6，7，10]，比较第I组中所有以3开头的填充物与15-3=12的填充物：

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，你将得到完全相同的填充物

现在考虑第二组的填充物，它们都是从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，你得到的填充物正好是第二组中的填充物。你知道吗

你可能想知道，为什么我在上一次调用fill时使用了[4，5，6，7，10]作为子长度，而不是[3，4，5，6，7，10]？这是因为我只感兴趣的填充物是越来越多的秩序，并开始与4。这排除了任何包含3的填充。你知道吗

最后，为了得到第三组中的填充物，使用子长度[5，6，7，10]，为15-5=10的所有填充物预加5：

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

---

如果你有这种倾向，你可以对每个小组重复同样的分析。例如，您可以根据它们的第一个元素对fill(15 - 3, [3, 4, 5, 6, 7, 10])生成的填充进行分组；您将得到4个组：

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

[4, 4, 4]

[5, 7]

[6, 6]

这些组是通过将3、4、5或6分别预先添加到所制备的填充物中而获得的

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

上面的分析只是“手工”完成fill函数所做的事情。你知道吗

需要注意的一点是，对于每个递归调用，问题都会变得更简单。你知道吗

例如，在生成filling[3，5，7]的过程中，执行了以下对fill的调用：

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。递归总是以这些琐碎情况的解结束。最终的解决方案由这些琐碎的解决方案组合而成。你知道吗