词典组合算法

Question

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

对我来说，这段代码生成以下组合（从0到3的4个中的2个：]

1. 0 1
2. 0 2
3. 1 2
4. 1 3
5. 2 3

但是缺少0 3。这是因为一旦将（2.）和（3.）中的0翻转为1，就无法从0开始。而是因为（2.）中0 2之间的差距大于1，所以0需要增加。我想念什么？因为它也应该生成0 3。

代码摘自《计算机编程的艺术》一书

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)产生：

1 0 
2 0 
2 1 
3 0 
3 1 
3 2 

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

这里是有关“词典”的各种含义以及Knuth的解释与其他比较的先前的discussion。