分裂陣列成固定Ñ塊具有動態尺寸

Question

我有一個數組說，

var a = [1,2,3,4,5];

其中欲分割成恰好n數塊，但具有在它的所有組合。

實施例：

當n=3應返回

combination1：[1],[2],[3,4,5]

combination2：[1,2],[3,4],[5]

combination3：[1,2,3],[4],[5]

combination4：[1,2],[3],[4,5]

combination5：[1],[2,3],[4,5]

combination6：[1],[2,3,4],[5]

我不能夠理解從哪裏開始和停止這樣的組合邏輯。任何形式的指針或幫助非常感謝。

Answer 1

您可以使用遞歸方法獲取所有嵌套的部分，並僅迭代剩餘數組的剩餘長度。

基本上，如果所需數組的長度等於項目數，則需要滿足退出條件。然後推送結果並退出該功能。

如果不是，則遍歷左邊的數組並將新零件移動到臨時數組。

function go(array, n) { 
 
    function iter(left, right) { 
 
     var i, 
 
      l = left.length - n + right.length + 1; 
 
     
 
     if (right.length + 1 === n) {     
 
      result.push(right.concat([left])); 
 
      return; 
 
     } 
 
     for (i = 1; i <= l; i++) { 
 
      iter(left.slice(i), right.concat([left.slice(0, i)])); 
 
     } 
 
    } 
 

 
    var result = []; 
 
    iter(array, []); 
 
    return result; 
 
} 
 

 

 
var array = [1, 2, 3, 4, 5], 
 
    n = 3, 
 
    result = go(array, n); 
 

 
result.forEach(function (a) { console.log(JSON.stringify(a)); });

Answer 2

我會使用一個略有不同的實現比尼娜。

function combinations(n, values, log){ 
 
    if(n > values.length) 
 
    throw new Error(`cannot divide ${values.length} items into ${n} groups`); 
 
    
 
    var results = [], 
 
    //you'll always have n items in your combination, by the very definition of this task 
 
    //this array holds the state/progress during the iterations, 
 
    //so we don't have to concat partial results all the time 
 
    //we'll push clones of the current state to the results. 
 
    combination = Array(n); 
 

 
    //just a utility to write a chunk to a particular index 
 
    function updateIndex(index, left, right){ 
 
    combination[index] = values.slice(left, right); 
 
    log && log(index, "updateIndex(" + [index, left, right] + ")", JSON.stringify(combination[index])); 
 
    } 
 
    
 
    //And by the good old Roman principle: divide et impera 
 
    //this function always processes a subset of the array, defined by the bounds: left and right. 
 
    //where `left <= index < right` (so it doesn't include right) 
 
    //it is a recursive function, so it processes one chunk at a time, and calls itself to process the rest of the array 
 
    function divide(index, chunks, left, right){ 
 
    log && log(index, "divide(" + [index, chunks, left, right] + ")", JSON.stringify(values.slice(left, right)) + " divided by " + chunks); 
 
    if(chunks > 1){ 
 
     //I have to divide my section of the array in mutliple chunks 
 
     //I do that by defining a pivot 
 
     //the range where I can pivot is limited: 
 
     // - I need at least 1 item to the left for the current chunk 
 
     // - and I need at least (chunks-1) items to the right for the remaining subdivisions 
 
     for(var pivot = left + 1; pivot <= right - (chunks-1); ++pivot){ 
 
     //everything on the left of this pivot is the current chunk 
 
     //write it into the combinations array at the particular index 
 
     updateIndex(index, left, pivot); 
 
     //everything on the right is not my buisness yet. 
 
     //I'll call divide() again, to take care of that 
 
     divide(index+1, chunks-1, pivot, right); 
 
     } 
 
    }else{ 
 
     //this is the last chunk, write this whole section to the last index 
 
     updateIndex(index, left, right); 
 
     //push a clone of this combination to the results 
 
     //because further iterations in the loops, will change the values of the original 
 
     //to produce the remaining combinations 
 
     results.push(combination.slice()); 
 
     log && log(index, "push(" + formatCombination(combination) + ")\n"); 
 
    } 
 
    return results 
 
    } 
 
    
 
    return divide(0, n, 0, arr.length); 
 
} 
 

 
function formatCombination(row){ 
 
    return JSON.stringify(row).replace(/\],\[/g, "], ["); 
 
} 
 

 
//an utility to log the steps in a nice fashion 
 
function logger(indentation, fnText, memo){ 
 
    var str = " ".repeat(indentation) + fnText; 
 
    console.log(memo? str + " ".repeat(60-str.length) + memo: str); 
 
} 
 

 

 
var arr = [0,1,2,3,4,5]; 
 
var result = combinations(3, arr, logger); 
 

 
console.log(); 
 
console.log(result.map(formatCombination).join("\n"))