1

取以下值：

0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0

我想创建一个生成 64x4 矩阵的函数，该矩阵由 256 个元素组成，其中包括上述 11 个值的每组，总和为 1

关于最有效的方法的任何帮助都会非常有帮助。

4

2 回答 2

2

以下代码可以满足您的需求。我使用了加到 10 的整数，以避免浮点舍入错误。您可能可以通过更早地跳出循环来使其运行得更快，并且在 raise 之前不要让它一直向下钻取StopIteration，但这会使代码变得不那么清晰。

def partitions(n=10, items=range(11), count=4) :
    if count == 0 and n == 0:
        yield []
    elif n < 0 or count < 0:
        raise StopIteration
    for j in xrange(len(items)) :
        ret = [items[j]]
        for k in partitions(n-items[j], items[j:], count-1) :
            yield ret + k

>>> [j for j in partitions()]
[[0, 0, 0, 10], [0, 0, 1, 9], [0, 0, 2, 8], [0, 0, 3, 7], [0, 0, 4, 6],
 [0, 0, 5, 5], [0, 1, 1, 8], [0, 1, 2, 7], [0, 1, 3, 6], [0, 1, 4, 5],
 [0, 2, 2, 6], [0, 2, 3, 5], [0, 2, 4, 4], [0, 3, 3, 4], [1, 1, 1, 7],
 [1, 1, 2, 6], [1, 1, 3, 5], [1, 1, 4, 4], [1, 2, 2, 5], [1, 2, 3, 4],
 [1, 3, 3, 3], [2, 2, 2, 4], [2, 2, 3, 3]]

我不太确定你是从哪里想到会有 64 个这样的子集的。上面的功能想出了

>>> len([j for j in partitions()])
23

4 个元素的有序子集。如果您不希望对子集进行排序，则可以通过调用partitionsfull来获得它items，而不是items[j:]在递归调用中。但是你得到

>>> len([j for j in partitions()])
286

如果您不将自己限制为 4 个元素的子集，那么我们必须摆脱0（有无限的子集加起来 10 和任意数量的零），然后我们正在计算 10 的分区，这是对生命、宇宙和一切的终极问题的答案，或者确切地说是42。

于 2013-03-12T13:03:32.350 回答
1

正如 Jaime 所说，动态编程在这里可能会被证明是有用的。您可以将此问题定义为对树的递归搜索，其中树中的每个节点都包含一些预先指定的元素。树的叶子包含所有总和为 1 的组合。

因此，在搜索的每一步：

  1. 选择下一个总和不超过 1 的数字。
  2. 将这个数字添加到你的数字集合中，这个集合将是下一个节点。
  3. 从此节点重复，直到到达离开节点（总和 == 1）。

一旦节点 N 以下的所有节点都被完全探索过，或者 N 是一个离开节点：转到其父节点并重复步骤 1 到 3。

于 2013-03-12T08:06:20.337 回答