C 代码排列

Question

这是一个排列代码，但它不会打印所有可能的排列。 只有打印的是输入。这段代码有什么问题？

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int bitmask;
char* characters;
int characters_count;
char* running;
int running_count;
void permutations() {
    int i;
    if (running_count == characters_count) {
        printf("%sn", running);
    } else {
        for (i=0; i<characters_count; i++) {
            if ( ((bitmask>>i)&1) == 0 ) {
                running[running_count] = characters[i];
                bitmask |= (1<<i);
                running_count = running_count + 1;
                permutations();
                running_count = running_count - 1;
            }
        }
    }
}
main() {
    int i;
    int cases;
    characters = (char*)malloc(sizeof(char)*30);
    scanf("%s", characters);
    characters_count = strlen(characters);
    running = (char*)malloc(sizeof(char)*30);
    memset(running, 0, 30);
    running_count = 0;
    permutations();
    free(characters);
    free(running);
}

示例输入

ab

示例输出

ab

而不是

ab
ba

我的朋友认为这里只有一行是错误的。但是我无法弄清楚哪条线是错误的或我缺少的线

Answer 1

您可以通过以下方式修复代码：

    bitmask |= (1<<i);
    running_count = running_count + 1;
    permutations();
    running_count = running_count - 1;
    bitmask &= ~(1<<i);

但是，不依赖全局变量会好得多。

考虑到固定的缓冲区大小，main中的内存分配也是不必要的。

这是一个没有内存分配的版本，不是全局变量：

#include <stdio.h>
#include <string.h>
void permutations(int bitmask,
                  const char *characters, int characters_count,
                  char *running, int running_count) {
    if (running_count == characters_count) {
        printf("%.*sn", running_count, running);
    } else {
        for (int i = 0; i < characters_count; i++) {
            if (((bitmask >> i) & 1) == 0) {
                running[running_count] = characters[i];
                permutations(bitmask | (1 << i),
                             characters, characters_count,
                             running, running_count + 1);
            }
        }
    }
}
int main(void) {
    char characters[30];
    char running[30];
    if (scanf("%29s", characters) == 1) {
        permutations(0, characters, strlen(characters), running, 0);
    }
    return 0;
}

另请注意%.*s printf转换说明符，用于仅打印 running 中的第一个running_count个字符，以及防止缓冲区溢出的%29s scanf说明符。