組合算法返回一個號碼的所有可能的組合物

我需要實現在Javascript，其中該結果將是相同的。隨着the figure on the right in Wikipedia給定數量（n）組合算法，該函數將能夠返回所有可能的分色，例如

2: [1,1], [2] (2 sets) 
3: [1,1,1], [1,2], [2,1], [3] (4 sets) 
4: [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2], [3,1], [1,3], [4] (8 sets)

理想的情況下，應該是一個函數接受並執行回調2^(n-1)倍。我會接受任何我能理解的語言（並從中重寫）的答案。謝謝！

來源

2011-12-04 timdream

對於你給n = 2,3或4的例子，它會是'2 ^（n-1）'不是嗎？ – nnnnnn

@prusswan感謝關鍵字。我自己寫了這個函數。 – timdream

Prusswan可能已經給出了最好的答案（該算法的名稱），但我忍不住寫一些javascript：

function separate(n, callback) { 
    for (var i=1; i<n; i++) { 
     separate(n-i, function(ret) { 
      ret.push(i); 
      callback(ret); 
     }); 
    } 
    callback([n]); 
}

來源

2011-12-04 14:07:08

+1。這非常優雅。我不知道關於算法的任何事情，我構建的版本是5倍（包括兩個輔助函數）。我不認爲用回調來幫助處理。 – nnnnnn

這是一個遞歸解決方案，它不依賴於使用回調（但另一種方式是將結果列表粘貼在一起，回調在這種情況下可以說是很好的）。無論如何，它的關鍵是該函數自己調用。 –

我的版本是遞歸的，但我決定讓我的函數緩存結果，以便如果您重複調用它的n值相同，它將從緩存中獲取結果，而不是從頭開始重新計算。這也意味着如果第一次調用是，例如n = 8，那麼當它返回結果時，緩存也將包含n = 7，n = 6，n = 5..n = 2的結果，因爲它們會得到在遞歸期間存儲。我預先在緩存中嵌入了n = 2的結果。對於n = 3，我複製了n = 2的結果並進行相應修改。等等。 – nnnnnn

就制定了功能上我自己：

/* Return all possibile compositions of a given natural number 
* callback will be called 2^n-1 times. 
* 
* ref: http://en.wikipedia.org/wiki/Composition_(number_theory) 
*/ 

function compositionsOf(n, callback) { 
    var x, a, j; 
    x = 1 << n-1; 
    while (x--) { 
     a = [1]; 
     j = 0; 
     while (n-1 > j) { 
      if (x & (1 << j)) { 
       a[a.length-1]++; 
      } else { 
       a.push(1); 
      } 
      j++; 
     } 
     callback.call(this, a); 
    } 
};

來源

2011-12-04 14:05:38 timdream

維基百科知道的關鍵知識：「每一種成分都與二進制數字匹配」。 – timdream

不錯，現在我知道如何做到這一點在JavaScript（但希望我永遠不會） – prusswan

def partition(i): 
    lst = [1] 
    while i: 
     if i & 1: 
      lst.append(1) 
     else: 
      lst[-1] += 1 
     i >>= 1 
    del lst[-1] 
    return lst

呼叫2 **（n-1）< = i < 2 ** n。

來源

2011-12-04 14:12:15 Per

組合算法返回一個號碼的所有可能的組合物

回答

相關問題