更改枚举算法以首先显示更大的范围

Question

我有一个需要枚举算法的程序，我是这样工作的:

#include <stdio.h>

void show (int subs[], int k) {
    int i;
    for (i=1; i<=k; i++)
        printf("%i ", subs[i]);
    puts("");
}

void enumerate (int n) {
    int subs[n+1], k = 0;
    *subs = 0;
    while (1) {
       if (subs[k] < n) {
            subs[k+1] = subs[k] + 1;
            k++;
        } else {
            subs[k-1] += 1;
            k--;
        }
        if (k == 0) break;
        show (subs, k);
    }
}

int main(void) {
    enumerate(4);
    return 0;
}

ideone

它应该是 O(2^N) 调用 show(subs, k)。最初，我认为这不会有任何问题，但我错了。实际上我的程序需要:

2 secs for n=25
4 secs for n=26
9 secs for n=27
18 secs for n=28
...

如您所见，它的时间增长得非常快。我的程序也进行了快速排序，而不是 show，它根据我的逻辑调用了另一个函数，但这并不重要。

但由于我必须更快地完成，我开始分析我的问题...

我说过，如果在序列 1 2 4 5(范围长度为 4)中找到我想要的解决方案，则范围长度小于该值的所有序列对我的逻辑来说都是毫无值(value)的。

然后，我尝试编写上面显示的 enumerate 函数，使范围更大的序列首先出现，因为如果我得到这个，我可以在找到时简单地破坏 enumerate 函数所需的值。

但经过大约两个小时的努力，我发现自己有 4 个内循环 (!!) 并且顺序错误。

各位忍者能帮帮我吗？提前致谢。

更新

如果你运行 enumerate(3) 你会得到:

1 
1 2 
1 2 3 
1 3 
2 
2 3 
3

我想要的，首先是更大的射程长度，所以:

1 2 3 
1 2 
1 3 
2 3 
1 
2 
3

Answer 1

首先，输出的大小像 2<sup>n</sup> 一样增长, 不是 n<sup>2</sup> .因此你的表现问题。重新排序可能会有所帮助，但重新思考您的算法可能会有更多帮助。

但话虽如此，这里有一个解决方案:

#include <stdio.h>

void show (int subs[], int k) {
    int i;
    for (i=1; i<=k; i++)
        printf("%i ", subs[i]);
    puts("");
}

void enumerate (int n) {
    int subs[n+1], k = n, l = 0;
    *subs = 0;
    // Populate subs with longest possible sequence.
    for (int i = 0; i < n + 1; i++) {
       subs[i] = i;
    }
    while (0 < k) {
       show(subs, k);
       // Find first increasible spot 
       l = 0;
       for (int i = k; 0 < i; i--) {
          if (subs[i] + k - i < n) {
             l = i;
             break;
          }
       }
       if (0 < l) {
          // Create our increasing sequence
          subs[l]++;
          for (int i = l+1; i <= n; i++) {
             subs[i] = subs[i-1] + 1;
          }
       }
       else {
          // Make k shorter and reset the sequence.
          k = k-1;
          for (int i = 0; i < n + 1; i++) {
             subs[i] = i;
          }
       }
    }
}

int main(void) {
    enumerate(4);
    return 0;
}