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

Question

想解决一个分堆问题，比如有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>

Answer 1

已知对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代码：

测试结果：

划分的数目叫做贝尔数。

Answer 2

问题已经解决，非常感谢萝卜同学的回答。

根据萝卜提到的贝尔数的概念，我又上网进行了搜索，找到了另外两种语言的实现，现在贴在下方：
有兴趣的同学可以来这里测试：
https://paiza.io/projects/new

代码来自这里：https://www.zhihu.com/questio...

1,Scala

object Main extends App{
    // Here your code !
    def ps[A]: Seq[A] => Iterator[Seq[Seq[A]]] = {
        case Seq() => Iterator(Nil)
        case x +: rs => (ps(rs) map (ys => List(x)+:ys)) ++
          (ps(rs) flatMap { ys => ys.indices map (i => ys.updated(i, x+:ys(i))) })
     }

    ps("abcd") foreach println
}

2,JAVA

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
    int n = 4;
       ArrayList<ArrayList<ArrayList<Integer>>> array = Partition(n);
    PrintResult(array);
    }
    
    private static ArrayList<ArrayList<Integer>> Clone(ArrayList<ArrayList<Integer>> element) {
    
       ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < element.size(); i++) {
          ArrayList<Integer> a = new ArrayList<Integer>();
          ArrayList<Integer> ca = (ArrayList<Integer>) element.get(i);
    for (int j = 0; j < ca.size(); j++)
             a.add(new Integer(ca.get(j)));
          result.add(a);
       }
    return result;
    }
    
    private static ArrayList<ArrayList<ArrayList<Integer>>> Partition(int n) {
       ArrayList<ArrayList<ArrayList<Integer>>> array = new ArrayList<ArrayList<ArrayList<Integer>>>();
    if (n == 1) {
          ArrayList<ArrayList<Integer>> a = new ArrayList<ArrayList<Integer>>();
          ArrayList<Integer> b = new ArrayList<Integer>();
          b.add(new Integer(1));
          a.add(b);
          array.add(a);
    return array;
       }
       ArrayList<ArrayList<ArrayList<Integer>>> tmpArray = Partition(n - 1);
    for (int i = 0; i < tmpArray.size(); i++) {
          ArrayList<ArrayList<Integer>> element = (ArrayList<ArrayList<Integer>>) tmpArray.get(i);
    
          ArrayList<ArrayList<Integer>> newelement = null;
    for (int j = 0; j < element.size(); j++) {
             newelement = Clone(element);
    
             ((ArrayList<Integer>) (newelement.get(j))).add(new Integer(n));
             array.add(newelement);
          }
          newelement = Clone(element);
          newelement = (ArrayList<ArrayList<Integer>>) element.clone();
          ArrayList<Integer> app = new ArrayList<Integer>();
          app.add(new Integer(n));
          newelement.add(app);
          array.add(newelement);
       }
    return array;
    }
    
    private static void PrintResult(ArrayList<ArrayList<ArrayList<Integer>>> array) {
    for (int i = 0; i < array.size(); i++) {
          ArrayList<ArrayList<Integer>> a = (ArrayList<ArrayList<Integer>>) array.get(i);
    for (int j = 0; j < a.size(); j++) {
             ArrayList<Integer> b = (ArrayList<Integer>) (a.get(j));
    for (int k = 0; k < b.size(); k++)
                System.out.print(b.get(k));
             System.out.print(" ");
          }
          System.out.println();
       }
    }
}

---

最新更新，已经找到javascript的解决方法。
参考自：https://blogs.msdn.microsoft....

    function Stirling(n, k, f) {
     if (n == 0 && k == 0) { f([]); return; }
     if (n == 0 || k == 0) { return; }
     Stirling(n-1, k, function(s) {
      for (var i = 0; i < k; i++) {
       s[i].push(n);
       f(s);
       s[i].pop();
      }
     });
     Stirling(n-1, k-1, function(s) {
      s.push([n]);
      f(s);
      s.pop();
     });
    }
    function logToConsole(s) {
      console.log(JSON.stringify(s));
    }
    function Bell(n, f) {
     for (var i = 1; i <= n; i++) {
      Stirling(n, i, f);
     }
    }

    Bell(3, logToConsole);

我简单翻译了一下那篇文章，链接在这里：http://blog.sina.com.cn/s/blo...