返回一个可变长度，其总和等于给定整数

在形式f(x,y,z)其中x是一个给定整数之和的序列，y是序列的最小长度，并且z是序列的最大长度。但现在让我们假装我们正在处理一个固定长度的序列，因为否则就需要很长时间才能写出问题。返回一个可变长度，其总和等于给定整数

所以我们的功能是f(x,r)其中x是给定的整数和r是序列在可能序列列表中的长度。

为x = 10，并r = 2，这些都是可能的组合：

让我们的商店，在Python作为对的列表：

[(1,9), (2,8), (3,7), (4,6), (5,5)]

所以使用的样子：

>>> f(10,2) 
[(1,9), (2,8), (3,7), (4,6), (5,5)]

回到最初的问题，一个序列返回的范围是(y,x)。我的形式f(x,y,z)，前面所定义的，并留出长度1（其中y-z == 0）的序列，这将如下所示：

>>> f(10,1,3) 
[{1: [(1,9), (2,8), (3,7), (4,6), (5,5)], 
    2: [(1,1,8), (1,2,7), (1,3,6) ... (2,4,4) ...], 
    3: [(1,1,1,7) ...]}]

所以输出是字典的一个列表，其中的值是对的列表。不完全最佳。

所以我的问题是：

是否有已经处理了这个库？
如果没有，有人可以帮我写两个我提到的功能吗？（首先是固定序列长度）？
由于我对相当微不足道的数学知识存在巨大差距，您是否可以忽略我的整数存储方法并使用最有意义的任何结构？

对不起，今天所有这些算术问题。谢谢！

来源

2011-03-31 Christopher O' Donnell

输出是元组列表 – highBandWidth 2011-03-31 20:41:23

您是否真的需要生成完整的序列列表？这似乎有点笨拙（更不用说慢）......也许更好的方法来看看这个是编写一个函数g（sum，nterms，index），它返回列表的索引序列所有序列的总和为'sum'的长度为'nterms'。我认为这会更容易 - 我强烈怀疑它最终会递归。 – 2011-03-31 20:47:05

这是下一步。 – 2011-03-31 21:16:18

的itertools模块将肯定是因为我们正在处理的前突变有益的 - 但是，这看起来很像一门功课的任务......

编辑：看起来很有趣的，所以我会做的尝试。

编辑2：这你想要什么？

from itertools import combinations_with_replacement 
from pprint import pprint 

f = lambda target_sum, length: [sequence for sequence in combinations_with_replacement(range(1, target_sum+1), length) if sum(sequence) == target_sum] 

def f2(target_sum, min_length, max_length): 
    sequences = {} 
    for length in range(min_length, max_length + 1): 
     sequence = f(target_sum, length) 
     if len(sequence): 
      sequences[length] = sequence 
    return sequences 

if __name__ == "__main__": 
    print("f(10,2):") 
    print(f(10,2)) 
    print() 
    print("f(10,1,3)") 
    pprint(f2(10,1,3))

输出：

f(10,2): 
[(1, 9), (2, 8), (3, 7), (4, 6), (5, 5)] 

f(10,1,3) 
{1: [(10,)], 
2: [(1, 9), (2, 8), (3, 7), (4, 6), (5, 5)], 
3: [(1, 1, 8), 
    (1, 2, 7), 
    (1, 3, 6), 
    (1, 4, 5), 
    (2, 2, 6), 
    (2, 3, 5), 
    (2, 4, 4), 
    (3, 3, 4)]}

来源

2011-03-31 20:39:05

f，f2，r，c ...我认为你应该为你的变量或函数使用有意义的单词。 – utdemir 2011-03-31 21:00:07

该OP只命名他们f，我真的不能想到更合乎逻辑的... – 2011-03-31 21:01:17

不是我的作业本身，但它确实计算我的作业。（这绝不是作弊。） – 2011-03-31 21:17:56

我只是写了递归发生器功能，你应该弄清楚如何获取列表出它自己的...

3210

编辑：我只是看到它不完全是你想要的，我的版本也生成重复只有排序不同。但是，您可以通过排序所有结果并检查重复的元组来简单地将它们过滤掉。

来源

2011-03-31 20:51:16 muksie

嵌套使得这个最具可读性。谢谢！ – 2011-03-31 21:41:13

该问题被称为Integer Partitions，并且已被广泛研究。

Here你可以找到一个纸比较几种算法（并提出一个特定）的性能，但也有很多遍净引用。

来源

2011-03-31 21:40:26

返回一个可变长度，其总和等于给定整数

回答

相关问题