按字母顺序打印子集，不排序

Question

我应该接收 n，并创建一个 1 到 n 的数组，然后按字母顺序打印子集，但目标是创建它们字母顺序（无数组排序），例如 n=3 正确的顺序是： {} {1} {1,2} {1,2,3} {1,3} {2} {2,3} {3}.

所以我当前的代码找到了子集：

    for (int code = 0; code < pow(2, n); code++) {
        printf("{");
        counter = 0;
        for (int i = 0; i < n; i++) {
            if (code & (1 << i)) {
                counter++;
                if (counter == 1)
                    printf("%d", nums[i]);
                else
                    printf(", %d", nums[i]);
            }
        }
        puts("}");
    }

问题是按要求的顺序打印它们，我想编写一个函数来按该顺序输出子集，而不进行任何排序。

我检查的另一种选择是 DFS/backtracking 算法，但即便如此，它们也不会按照要求的确切顺序打印。

所以我想知道 DFS 是否是正确的路径（经过修改）或者是否有另一种算法更适合我？

Answer 1

如果你想按字母顺序打印一个数组，而你不能对数组进行排序，那么你必须按照所需的顺序将元素插入数组中。用你按顺序插入它们的子集创建一个新数组并将其传递给打印函数，我建议你为子集创建一个比较函数。

Answer 2

为了实现您的目标，您可以使用执行以下步骤的递归函数：

从一个空集开始，索引 i 在 0。
打印当前集合
增加i到下一个数字
如果i超过最大数量，停止
将数字 i 添加到集合中并在第 2 步递归
删除数字 i 并在第 3 步迭代

这是一个简单的实现：

#include <stdio.h>
#include <stdlib.h>

static void printset(const int set[], int n) {
    printf("{");
    for (int i = 0; i < n; i++) {
        if (i > 0)
            printf(",");
        printf("%d", set[i]);
    }
    puts("}");
}

static void printsets(int set[], int count, int i, int n) {
    printset(set, count);
    while (++i <= n) {
        set[count] = i;
        printsets(set, count + 1, i, n);
    }
}

int main(int argc, char *argv[]) {
    int n;
    if (argc > 1) {
        n = strtol(argv[1], NULL, 0);
    } else {
        printf("Enter n: ");
        if (scanf("%d", &n) != 1)
            return 1;
    }
    int set[n];
    printsets(set, 0, 0, n);
    return 0;
}

这是一个变体，它可以在大约 10 秒内按字母顺序打印所有 67108864 个字母表子集：

#include <stdio.h>

static void printsets(char set[], int len, char c) {
    printf("%.*s\n", len, set);
    while (c <= 'Z') {
        set[len] = c;
        printsets(set, len + 1, ++c);
    }
}

int main() {
    char set[26];
    printsets(set, 0, 'A');
    return 0;
}

按字母顺序打印子集，不排序

print subsets in alphabetic order, without sorting

c

arrays

algorithm

subset

sub-array