递归生成瓷砖排列并验证回文的C代码功能解析求助

这段C语言代码的核心是统计10块瓷砖的所有全排列中，能拼接成回文字符串的排列总数。以下是各部分的详细运行逻辑：

全局定义与常量 #

• #define N 10：固定瓷砖总数为10
• #define MAXLEN 5：限制单块瓷砖的最大字符长度（包含字符串终止符）
• MYTILES[N][MAXLEN]：硬编码存储10块瓷砖的具体字符内容

main函数：程序入口 #

1. 初始化两个数组：
   • perm[N]：记录当前生成的排列（存储瓷砖的索引值）
   • used[N]：标记每块瓷砖是否已被选入当前排列（初始全为0，表示未使用）
2. 调用递归函数go启动全排列生成与验证流程，接收返回的符合条件的排列数量
3. 打印最终统计结果

go函数：递归生成全排列（回溯法） #

这是生成所有可能排列的核心函数，用回溯法遍历所有组合：

• 参数说明：
  • perm：当前已确定的排列部分
  • used：瓷砖使用状态标记
  • k：当前正在填充排列的第k个位置（从0开始计数）
  • tiles：存储瓷砖字符的数组
• 终止逻辑：当k == N时，说明已生成完整的10块瓷砖排列，调用eval函数验证该排列拼接后是否为回文，返回1（是回文）或0（不是）
• 递归流程：
  1. 遍历所有10块瓷砖，跳过已标记为used[i] = 1的瓷砖
  2. 标记当前瓷砖为已使用（used[i] = 1），将其索引存入perm[k]
  3. 递归调用go函数，填充排列的下一个位置（k+1）
  4. 递归返回后，将当前瓷砖的使用标记重置为0（回溯，尝试下一种可能）
  5. 累加所有递归返回的符合条件的数量，最终返回统计结果

eval函数：验证拼接字符串是否为回文 #

负责将排列转化为完整字符串并验证回文属性：

1. 创建临时字符数组tmp，按排列顺序将每块瓷砖的字符逐一拼接进去，最后添加字符串终止符\0
2. 从字符串两端向中间逐一比对对称位置的字符：
   • 如果任意一对对称字符不相等，直接返回0（不是回文）
   • 如果所有对称字符都匹配，返回1（是回文）

完整代码 #

#include <stdio.h>
#include <string.h>

#define N 10
#define MAXLEN 5

int go(int perm[], int used[], int k, char tiles[N][MAXLEN]);
int eval(int perm[], char tiles[N][MAXLEN]);

char MYTILES[N][MAXLEN] = {
    "at", "ta", "g", "cc", "ccac", "ca", "cc", "gag", "cga", "gc"
};

int
main(void)
{
    int perm[N];
    int used[N];

    for (int i = 0; i < N; i++)
        used[i] = 0;

    int res = go(perm, used, 0, MYTILES);

    printf("Number of tile orderings that create palindromes is %d\n", res);

    return 0;
}

int
go(int perm[], int used[], int k, char tiles[N][MAXLEN])
{
    if (k == N)
        return eval(perm, tiles);
    int res = 0;

    for (int i = 0; i < N; i++) {
        if (used[i])
            continue;
        used[i] = 1;
        perm[k] = i;
        res += go(perm, used, k + 1, tiles);
        used[i] = 0;
    }

    return res;
}

int
eval(int perm[], char tiles[N][MAXLEN])
{
    char tmp[N * MAXLEN];
    int idx = 0;

    for (int i = 0; i < N; i++) {
        int len = strlen(tiles[perm[i]]);

        for (int j = 0; j < len; j++)
            tmp[idx++] = tiles[perm[i]][j];
    }
    tmp[idx] = '\0';
    for (int i = 0; i < idx / 2; i++)
        if (tmp[i] != tmp[idx - 1 - i])
            return 0;
    return 1;
}

内容的提问来源于stack exchange，提问作者Amy Nguyen