Javascript 中的组合算法返回数字的所有可能组合

Question

编辑：

我需要在Javascript中实现组合算法，其结果与维基百科右侧的数字。使用给定的数字（n），该函数将能够返回所有可能的分隔，例如

2: [1,1], [2] (2 sets)
3: [1,1,1], [1,2], [2,1], [3] (4 sets)
4: [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2], [3,1], [1,3], [4] (8 sets)

理想情况下应该是一个函数接受并执行回调2^(n-1)次。我会接受任何我能理解（并重写）的语言的答案。谢谢！

Answer 1

Prusswan 可能已经给出了最好的答案（算法的名称），但我忍不住写了一些 JavaScript：

function separate(n, callback) {
    for (var i=1; i<n; i++) {
        separate(n-i, function(ret) {
            ret.push(i);
            callback(ret);
        });
    }
    callback([n]);
}

Answer 2

刚刚自己搞定了这个功能：

/* Return all possibile compositions of a given natural number
* callback will be called 2^n-1 times.
*
* ref: http://en.wikipedia.org/wiki/Composition_(number_theory)
*/

function compositionsOf(n, callback) {
    var x, a, j;
    x = 1 << n-1;
    while (x--) {
        a = [1];
        j = 0;
        while (n-1 > j) {
            if (x & (1 << j)) {
                a[a.length-1]++;
            } else {
                a.push(1);
            }
            j++;
        }
        callback.call(this, a);
    }
};

Answer 3

def partition(i):
    lst = [1]
    while i:
        if i & 1:
            lst.append(1)
        else:
            lst[-1] += 1
        i >>= 1
    del lst[-1]
    return lst

要求 2**(n-1) <= i < 2**n。