排列组合算法

在此之前写下最近的知识盲点：

全局变量没初始化的情况下是0；而局部变量在没有初始化的情况是以前遗留在内存中的垃圾数据。

------------------------------------------------------------------------------------------------------

同样引用了大神YzlCoder的16年蓝桥杯解答第六题

第六题：

方格填数

如下的10个格子

（如果显示有问题，也可以参看【图1.jpg】）

填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

实现代码：

    #include <stdio.h>  
    #include <math.h> 
	#include<stdbool.h> //使用bool型需要的库 
    int flag[3][4]; //表示哪些可以填数  
    int mpt[3][4]; //填数  
    bool visit[10];  //在DEV C++中测试过C/C++中bool的默认值是0 
    int ans = 0;
    int run=0; 
    void init()   //初始化  
    {  
        int i,j;  
        for(i = 0 ; i < 3 ; i ++)  
            for(j = 0 ; j < 4 ; j ++)  
                flag[i][j] = 1;  
        flag[0][0] = 0;  
        flag[2][3] = 0;  
    }  
      
    void Solve()  
    {  
    	int i,j,k;
        int dir[8][2] = { 0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};  
        int book = true;  
        for(i = 0 ; i < 3 ; i ++)  
        {  
            for(j = 0 ; j < 4; j ++)  
            {  
                //判断每个数周围是否满足  
                if(flag[i][j] == 0)continue;  
                for(k = 0 ; k < 8 ; k ++)  
                {  
                    int x,y;  
                    x = i + dir[k][0];  //此处极其精彩，思想是将(i,j)作为坐标原点，
		    y = j + dir[k][1];	//而dir[8][2]每行(如(0,1),(0,-1))则标示
                                        //相对于(i,j)的偏移位置。
				        //一共有8行分别代表(i,j)的上下左右四个对角
                    if(x < 0 || x >= 3 || y < 0 || y >= 4 || flag[x][y] == 0) continue;  
                    if(abs(mpt[x][y] - mpt[i][j]) == 1)  book = false;  
                }  
            }  
        }  
        if(book) ans ++;  
    }  
      
    // 关键算法，组合算法。 
    void dfs(int index)  
    {  
        int i,x,y;  
        x = index / 4;  
        y = index % 4;  
        if( x == 3)          //x=3时index=12一次赋值完毕，接下来用Solve验证
		             //时候满足"连续的两个数字不能相邻"这个条件。 
        {  
            Solve();  
            return;  
        }  
        if(flag[x][y])  
        {  
            for(i = 0 ; i < 10 ; i ++)//虽然博主说过0-9不可以重复使用但是此处每个格子都赋值0-9，
				      //不过没关系Solve()中又判断if(abs(mpt[x][y] - mpt[i][j]) == 1) 
            {  
                if(!visit[i])  
                {   
                    visit[i] = true;  
                    mpt[x][y] = i;   
                    dfs(index+1);     //在for循环中嵌套递归！
                    visit[i] = false;  
                } 
            }  
        }  
        else  
        {  
            dfs(index+1);  
        }  
    }  
    int main()  
    {
        init();  
        dfs(0);  
        printf("%d\n",ans); 
        return 0;  
    }  

补充关于排列组合的一般性算法：

void combine(int pos,int h,const int n,const int r)
{
    int i;
    /*如果已选了r个元素了，则打印它们*/
    if (pos == r)
    {
        for(i=0; i<r; i++)
            cout<<s[p[i]];
        cout<<endl;
        return;
    }
    for(i=h; i<=n-r+pos; i++) /*对于所有未用的元素*/
    {
        if (!used[i])
        {
            /*把它放置在组合中*/
            p[pos] = i;
            /*使用该元素*/
            used[i] = 1;
            /*搜索第i+1个元素*/
            combine(pos+1,i+1,n,r);
            /*恢复递归前的值*/
            used[i] = 0;
        }
    }
}

Quotation: https://www.cnblogs.com/yangmingyu/p/6927741.html