javascript - 排列组合中的分堆可能性问题

问题描述

问 题

想解决一个分堆问题，比如有a,b,c三个物体，列出所有可能的组合方法。
三个物体的话有5种可能性。
function all_groups(arr){
}
输入数组：[a,b,c]
输出数组：
[

[[a],[b],[c]],
[[a,b],[c]],
[[a],[b,c]],
[[a,c],[b]],
[[abc]]

]

应该是一个需要用到动态规划，递归计算的问题。
目前遍历的时候遇到了一个问题，就是如何根据物品个数，得到所有的拆分方法。
进一步分解问题为，列出有k个物品，分成n堆的，所有方法。
function group_divide(k,n){
}
比如将5个物品分成2堆，有2种分法。一堆1个，一堆4个，或者一堆2个，一堆3个。(0,5这种分法，我认为应该属于1堆。)
输入：group_divide(5,2)
结果为：[[1,4],[2,3]]

输入：group_divide(5,3)
结果为：[[1,1,3],[1,2,2]]

输入：group_divide(5,4)
结果为：[[1,1,1,2]]

输入：group_divide(6,2)
结果为：[[1,5], [2,4], [3,3]]

输入：group_divide(6,3)
结果为：[[1,2,3], [2,2,2]]

输入：group_divide(6,4)
结果为：[[1,1,2,2], [1,1,1,3]]

对于group_divide 和 all_groups的方法，你们有什么好的实现吗？

我列出一下我自己在网上找到的或者我自己写的大家可能用到的方法：

<script>
    //列出所有组合方法
    //输入：combination([1,2,3], 2)
    //输出：[[1,2],[1,3],[2,3]]
function combination (arr, size) {
  var r = []; //result

  function _(t, a, n) { //tempArr, arr, num
    if (n === 0) {
      r[r.length] = t;
      return;
    }
    for (var i = 0, l = a.length - n; i <= l; i++) {
      var b = t.slice();
      b.push(a[i]);
      _(b, a.slice(i + 1), n - 1);
    }
  }
  _([], arr, size);
  return r;
}
console.debug(JSON.stringify(combination([1,2,3], 2)));

    //列出所有排列方法
    //arrangement([1,2,3], 2)
    //输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
function arrangement(input) {
  var permArr = [],
  usedChars = [];
  function main(input){
    var i, ch;
    for (i = 0; i < input.length; i++) {
      ch = input.splice(i, 1)[0];
      usedChars.push(ch);
      if (input.length == 0) {
        permArr.push(usedChars.slice());
      }
      main(input);
      input.splice(i, 0, ch);
      usedChars.pop();
    }
    return permArr;
  }
  return main(input);
}
console.debug(JSON.stringify(arrangement([1,2,3])));


//去重
/*输入 var arr = [
      [[1,2],[3,4]],
      [[1,3],[2,4]],
      [[1,4],[3,2]],
      [[3,4],[1,2]],
      [[3,1],[2,4]]
    ];
    */
//输出：[[["1","2"],["3","4"]],[["1","3"],["2","4"]],[["1","4"],["2","3"]]]
function remove_duplicate(arr){
  var newArr = [];
  var stringArr = [];
  for (i = 0; i < arr.length; i++) {
    var inString = [];
    for (j = 0; j < arr[i].length; j++) {
      inString[j] = arr[i][j].sort().join("_");
    }
    var outString = inString.sort().join("|");
    if(stringArr.indexOf(outString) === -1) {
      stringArr.push(outString);
    }
  }
  for (i = 0; i < stringArr.length; i++) {
    var outArr = stringArr[i].split("|");
    newArr[i] = [];
    for (j = 0; j < outArr.length; j++) {
      var inArr = outArr[j].split("_");
      newArr[i][j] = inArr;
    }
  }
  return newArr;
}

    var arr = [
      [[1,2],[3,4]],
      [[1,3],[2,4]],
      [[1,4],[3,2]],
      [[3,4],[1,2]],
      [[3,1],[2,4]]
    ];
    console.debug(JSON.stringify(remove_duplicate(arr)));


//var a1 = ['a', 'b'];
//var a2 = ['a', 'b', 'c', 'd'];
//return ["c", "d"]
function arr_diff (a1, a2) {
  var a = [], diff = [];
  for (var i = 0; i < a1.length; i++) {
      a[a1[i]] = true;
  }
  for (var i = 0; i < a2.length; i++) {
      if (a[a2[i]]) {
          delete a[a2[i]];
      } else {
          a[a2[i]] = true;
      }
  }
  for (var k in a) {
      diff.push(k);
  }
  return diff;
};

//补充数组
//输入combination_left ([1,2], [1,2,3])
//输出[[1,2],[3]]
function combination_left (arr, oArr) {
  var newArr = [];
  for (var i = 0; i < arr.length; i++) {
    var diff = arr_diff(oArr, arr[i]);
    newArr[i] = [];
    newArr[i][0] = arr[i];
    newArr[i][1] = diff;
  }
  return newArr;
}

    </script>

解决方案

已知对n元素集合的所有划分parts(n)，怎么递归到parts(n+1)？

比如有一个对{1,2,3}的划分是

• {1,2}, {3}

那么可以通过在不同地方添加元素4把它扩充为对{1,2,3,4}的划分。可以把4做为一个新的子集：

• {1,2}, {3}, {4}

还可以把4添加到每个原有子集的内部：

• {1,2,4}, {3}

• {1,2}, {3,4}

容易证明，parts(4)的每个划分都可以用上面的方法扩充parts(3)的某个划分得到，而且这种扩充不会产生重复的结果。

使用以上算法的Mathematica代码：

测试结果：

划分的数目叫做贝尔数。

这篇关于javascript - 排列组合中的分堆可能性问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！