找到所有组合之和为N时指数

-1

乘以给定数量的项目（ñ），什么是生成所有可能的列表[A 最有效的方式，一个，...的状况下一个_ñ]的非负整数的是：找到所有组合之和为N时指数

1 *一个 + 2 *一个 + 3 *一个 + ... + N *一个_ñ = n

使用Python？

因此，例如，给定的5的n，下面的组合是：

[0,0,0,0,1]

[1,0,0,1,0]

[0,1,1,0,0]

[2,0,1,0,0]

[1,2,0,0,0]

[3 ，1,0,0,0]

[5,0,0,0,0]

我实现了生成的所有排列，然后，如果该列表满足上述要求检查，但有一个更有效的方式蛮力方法去做这个？

来源

2016-09-04 user3277533

@idjaw：存在实际问题（即效率）。我的理解是[效率问题在堆栈溢出上是有效的]（http://meta.stackexchange.com/questions/215282/is-stack-overflow-the-right-place-to-ask-a-question-about-码效率）。 – user3277533

我编辑了问题的开头，使其更清晰。请注意，关于组合生成的问题通常是这样的：显示暴力代码的代码是无用的：这既是显而易见的，也是无益的。很高兴听到OP的声明：“我已经实施了一种生成所有排列组合的强力方法，然后检查列表是否满足上述要求”，并且很高兴他们不费心去展示它;-)高效在这个领域中的代码（他们问的）通常与仅仅有效的暴力代码几乎没有任何关系。 –

“贪婪”算法对此很有效。我使用Python 3浏览：

def pick(total): 

    def inner(highest, total): 
     if total == 0: 
      yield result 
      return 
     if highest == 1: 
      result[0] = total 
      yield result 
      result[0] = 0 
      return 
     for i in reversed(range(total // highest + 1)): 
      result[highest - 1] = i 
      newtotal = total - i * highest 
      yield from inner(min(highest - 1, newtotal), 
          newtotal) 

    result = [0] * total 
    yield from inner(total, total)

然后，例如，

for x in pick(5): 
    print(x)

显示：

[0, 0, 0, 0, 1] 
[1, 0, 0, 1, 0] 
[0, 1, 1, 0, 0] 
[2, 0, 1, 0, 0] 
[1, 2, 0, 0, 0] 
[3, 1, 0, 0, 0] 
[5, 0, 0, 0, 0]

最喜欢的递归算法，它更或多或少显而易见的事情，然后递归解决剩下的（子）问题。

这里inner(highest, total)表示使用不大于highest的整数找到total的所有分解。我们可以使用多少份highest？这个比较明显的答案是，我们可以使用0,1,2，...，直到（包括）total // highest副本，但不超过这个。除非highest是1 - 那么，我们必须使用的1

我们使用的highest然而，许多副本究竟total份，其余的子问题分解使用整数总的一切依然不比highest - 1大。通过min(highest - 1, newtotal)而不是highest - 1是一种优化，因为尝试任何大于新总数的整数都是毫无意义的。

来源

2016-09-04 02:18:53

找到所有组合之和为N时指数

回答

相关问题