javascript - 将数组拆分为固定的 n 个具有动态大小的 block

Question

我有一个数组，

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

我想将其拆分为恰好 n 个 block ，但其中包含所有组合。

示例:

何时n=3应该返回

组合1:[1],[2],[3,4,5]

组合2:[1,2],[3,4],[5]

组合3:[1,2,3],[4],[5]

组合4:[1,2],[3],[4,5]

组合5:[1],[2,3],[4,5]

组合6:[1],[2,3,4],[5]

我无法理解从哪里开始和停止这个组合逻辑。非常感谢任何类型的指示或帮助。

Answer 1

我会使用与 Nina 略有不同的实现。

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") )