字典序组合算法

Question

词典组合算法如何找到所有可能的组合？

对我而言，此代码生成以下组合（4 个中的 2 个，从 0 到 3）：

0 1
0 2
1 2
1 3
2 3

但是 0 3 不见了。这是因为一旦从 (2.) 和 (3.) 中将 0 翻转为 1，就无法从 0 重新开始。但是因为 (2.) 中 0 2 之间的差距大于 1 即 0需要递增。我错过了什么？因为它也应该生成 0 3。

代码来自书本"The Art of computer programming"

Answer 1

确实生成了组合 (0 3)，只是不在您预期的位置。

这里直接把算法翻译成Java:

static void lex(int t, int n)
{
    int[] c = new int[t+3];
    for(int j=1; j<=t; j++) c[j] = j-1;
    c[t+1] = n;
    c[t+2] = 0;

    while(true)
    {
        for(int i=t; i>=1; i--) 
            System.out.print(c[i] + " ");
        System.out.println();

        int j=1;
        while(c[j]+1 == c[j+1])
        {
            c[j] = j-1;
            j += 1;
        }

        if(j > t) return;

        c[j] += 1;
    }
}

lex(2, 4) 产生：

这当然是有序的，只是如果您认为 0 应该在 1 之前等等，这不是您期望的顺序。

这是关于 "lexicographic" 的各种含义以及 Knuth 的解释与其他人的比较的先前 discussion。

字典序组合算法

Lexicographic combination algorithm

algorithm

combinatorics