查找陣列項目的nCr組合

Question

我有一個遞歸函數的問題，在Array中查找nCr對象。
此功能僅在r=2時表示僅在內部進入1級時纔有效。

看來我暫時'a'數組被全亂了的時候r > 2

// find nCr combinations in Array 
// n -> keys.length 
// r -> number of combination to extract (cross = r-1) 

console.clear(); 
var keys = [0,1,2,3,4,5]; 

// cross = 'r'-1, s = start point, a = array 
function recursive(cross, s, a){ 
    for(var i=s; i < keys.length; i++){ 
     if(!cross){ 
      var b = a.slice(0); 
      b.push(keys[i]); 
      set.push(b); 
     } 
     else{ 
      a.splice(-1, 1); 
      a.push(keys[i]); 
      recursive(cross-1, i+1, a); 
     } 
    } 
} 

var set = []; 
recursive(1, 0, []); 
console.log(set); 

Answer 1

我不知道你想在你的else狀況到底該怎麼做：注意a.splice(-1,1)消除了a最後一個元素，但是當你沒有東西需要移除時，你可以從a開始。即使代碼適用於r=2，這也表示您做錯了什麼。 （實際上，每當你進入更深層次時，a的起始元素數量與之前的水平相同，因此您將刪除某些不應觸及的元素。）

這是一個非常微小的修改您的算法，正常工作。我只是改變了else條件中的語句順序。

var keys = [0,1,2,3,4,5]; 

function recursive(cross, s, a) { 
    for(var i=s; i < keys.length; i++){ 
     if(!cross){ 
      var b = a.slice(0); 
      b.push(keys[i]); 
      set.push(b); 
     } 
     else{ 
      a.push(keys[i]); 
      recursive(cross-1, i+1, a); 
      a.splice(-1, 1); 
     } 
    } 
} 

var set = []; 
recursive(4, 0, []); 
console.log(set); 

最後這部分應該打印所有（6選擇5）= 5種元素的6種組合出keys。

這個想法是，現在在函數的每次調用中，splice只會刪除在該調用中添加的元素，而不是某些其他函數調用中添加的某個元素，可能在某個其他級別。這也保證a在開始時保持不變。 （你添加的所有東西都會再次刪除）

這是您在編寫遞歸函數時會看到的常見模式：執行一些修改，遞歸調用函數，然後執行一些反轉修改的清理。

順便說一句，稍乾淨的代碼（沒有cross = r-1混淆）在the first revision of this answer。