fuza.c

《数据结构-使用C语言》第三版

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

#define element_num 6    /*数字总数*/

int element[] = {1, 2, 2, 3, 4, 5};    /*数字*/
int output[element_num];    /*输出序列*/
_Bool used[] = {0, 0, 0, 0, 0, 0};    /*是否已经存在于输出序列中的flag数组*/
int count;    /*合法排列个数的计数器*/

void screen_out()    /*屏幕输出合法排列*/
{
    int i;
    for(i = 0; i < element_num; ++i)
printf("%d ", output[i]);
    
    printf("\n");
    count++;
}
/*判断当前的部分排列是否合法，包括元素是否重复，排列是否重复，是否符合题目限制*/
_Bool unused_legal_single(int current_pos, int element_index)
{
    if(used[element_index])    /*用于扩展当前序列的元素是否尚未被使用*/
return false;
    
    if(current_pos - 1 >= 0)    /*3和5是否相邻*/
    {
if(output[current_pos - 1] == 3 && element[element_index] == 5 ||
   output[current_pos - 1] == 5 && element[element_index] == 3)
    return false;

if(current_pos == 2 && element[element_index] == 4)    /*4是否是当前扩展元素并将扩展于位置3*/
    return false;
    }
    
    if(element_index == 2 && used[1] == false)    /*在扩展第二个2的时候判断第一个2是否已经被用过，凡是扩展第二个2时第一个2尚未用过的情况均重复于扩展第一个2时第二个2尚未用过的情况*/
return false;
    
    return true;
}

void enumerate(int current_pos)    /*递归生成排列。排列从短到长生成*/
{
    int i;
    
    if(current_pos == element_num)    /*如果排列已经完整，则输出*/
    {
screen_out();
return;
    }
    
    for(i = 0; i < element_num; ++i)
    {
if(unused_legal_single(current_pos, i))    /*如果当前扩展的序列已经不合法，则不需要继续将其扩展，可停止。否则继续扩展直到完整生成一个排列。凡有机会完整生成的排列均合法。*/
{
    output[current_pos++] = element[i];
    used[i] = true;
    enumerate(current_pos);
    current_pos--;
    used[i] = false;
}
    }
}

int main(int argc, char** argv) 
{
    count = 0;    /*初始化计数器*/
    enumerate(0);    /*从位置0开始扩展排列并输出合法结果*/
    printf("Total output: %d\n", count);
    getchar();
    return (EXIT_SUCCESS);
}