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("%s\n", 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

我的 friend 认为这里只有一行是错误的。但我不知道哪一行是错误的或我缺少哪一行

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("%.*s\n", 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 说明符。