棋子排列问题
用给定数量的红、绿、蓝三种颜色棋子排成一个圆环，要求任意相邻的棋子不能同色。棋子总数不超过20，每种颜色至少有1个棋子。求满足上述要求的全部排列结果，输出排列总数和所有排列结果（不考虑循环相似的），每行显示一种排列结果（分别用字母R、G、B表示红、绿、蓝），并记录到文件result.txt中。
/*
棋子排列问题
用给定数量的红、绿、蓝三种颜色棋子排成一个圆环，要求任意相邻的棋子不能同色。
棋子总数不超过20，每种颜色至少有1个棋子。求满足上述要求的全部排列结果，
输出排列总数和所有排列结果（不考虑循环相似的），每行显示一种排列结果（
分别用字母R、G、B表示红、绿、蓝），并记录到文件result.txt中。
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_COLOR 3
#define MIN_N 3
#define MAX_N 20
// 颜色的字母符号
static char *color_names = "RGB";
// 颜色的顺序值
enum {
RED = 0,
GREEN,
BLUE,
};
/* ----------------------------------------------------------------------------
* 算法思路:
* 因为相邻棋子不能同色, 所以一个n个棋子的排列可以用一个(n-1)位的二进制数表示.
* 假设RGB三色分别用0,1,2表示。第一个固定为某个颜色, 下一个颜色有2种可能
* (当前颜色+1或+2), 分别用0和1表示. 则算法简化为遍历2 ^ (n-1), 判断是否满足3种
* 颜色都有, 即可. 同时因为不需要考虑循环相似, 所以不用额外做变化和记录.
*/
int main(void)
{
FILE *fd = NULL;
int n; // 棋子个数
unsigned long x; // 当前排列的二进制表示
unsigned long end; // 当前排列的最后一个数字
unsigned long y; // 用于当前排列按位输出
unsigned long cur_color; // 当前位对应的颜色
unsigned char used[MAX_COLOR]; // 标记某个颜色是否用过
unsigned char all_used; // 计算是否所有颜色都用了
char colors[MAX_N + 1]; // 当前排列的具体颜色值
char colors_R[MAX_N + 1]; // 红色开始的排列
char colors_G[MAX_N + 1]; // 绿色开始的排列
char colors_B[MAX_N + 1]; // 蓝色开始的排列
int i; // 循环变量
int count = 0; // 总数
fd = fopen("result.txt", "w");
if (NULL == fd) {
printf("can't open result.txt\n");
return 0;
}
memset(colors, 0x00, (MAX_N + 1) * sizeof(char));
memset(colors_R, 0x00, (MAX_N + 1) * sizeof(char));
memset(colors_G, 0x00, (MAX_N + 1) * sizeof(char));
memset(colors_B, 0x00, (MAX_N + 1) * sizeof(char));
// 最少3个, 最多20个, 第一个颜色可以固定, 实际只要计算 n - 1 位的排列
for (n = MIN_N - 1; n < MAX_N; n++) {
end = (1ul << n) - 1;
for (x = 0; x <= end; x++) {
used[0] = used[1] = used[2] = 0; // 简单的赋值, 比循环更快
y = x;
cur_color = RED;
used[cur_color] = 1;
colors[0] = cur_color;
for (i = 0; i < n; i++) {
cur_color = (cur_color + 1 + (y & 0x01ul)) % MAX_COLOR;
y >>= 1;
used[cur_color] = 1;
colors[i + 1] = cur_color;
}
all_used = used[0] & used[1] & used[2];
if (all_used) { // 符合条件, 可以输出
count += 3;
for (i = 0; i <= n; i++) {
// 分别计算3种颜色开头的排列字符串
colors_R[i] = color_names[colors[i]];
colors_G[i] = color_names[(colors[i] + 1) % MAX_COLOR];
colors_B[i] = color_names[(colors[i] + 2) % MAX_COLOR];
}
fprintf(fd, "%s\n%s\n%s\n", colors_R, colors_G, colors_B);
}
}
}
printf("total: %d\n", count);
fclose(fd);
return 0;
}