找到所有組合之和爲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時指數

回答

相關問題