JAVA全排列！！！

￡神魔★判官ぃ 2022-06-14 00:13 133阅读 0赞

在各类比赛中，运用到全排列的方法的题有很多，有很多完成全排列的方法。例如：下面介绍两种运用递归实现的全排列，并通过蓝桥杯试题进行验证。

一、方法一：利用递归，逐渐将后面的数字互换位置，进而实现全排列。因为递归本身就不是很好理解所以下面给出实现的代码，通过代入数据可以加快理解，其中形参数组a存储了1-9个数字，n的值为0：

public static void fun(int a[], int n) {
    		if (n == 9) {
    			//此时的数组a已经完成了一种全排列
    		} else
    			for (int i = n; i < 9; i++) {
    				{
    					int temp = a[i];
    					a[i] = a[n];
    					a[n] = temp;
    				}
    				fun(a, n + 1);
    
    				{
    					int tamp = a[i];
    					a[i] = a[n];
    					a[n] = tamp;
    				}
    			}
    	}

因为这种方法没有涉及到大小值得比较，所以对于不同的字符进行全排列仍然可以实现：

public static void fun(char a[], int n) {
    			if (n == 9) {
    				//此时已经完成其中的一种全排列
    			} else
    				for (int i = n; i < 9; i++) {
    					{
    						char temp = a[i];
    						a[i] = a[n];
    						a[n] = temp;
    					}
    					fun(a, n + 1);
    
    					{
    						char tamp = a[i];
    						a[i] = a[n];
    						a[n] = tamp;
    					}
    				}
    		}

二、方法二：仍然使用递归进行实习，与上一种方法比较类似，只是在初始方面没有对数组进行赋值，而是再循环中进行实现：

private static void dfs(int[] a, boolean[] visit, int num) {  
            if (num==11) {  
                //此时完成其中一种全排列
            }  
            for (a[num] = 0; a[num] < 10; a[num]++) {  
                if (visit[a[num]]==false) {  
                    visit[a[num]]=true;  
                    num = num + 1;  
                    dfs(a, visit, num);  
                    num = num - 1;  
                    visit[a[num]]=false;  
                }  
            }  
        }

三、下面介绍在蓝桥杯涉及到的题

1、反幻方：使用的是上文提到的第一种方法

我国古籍很早就记载着

2 9 4   
7 5 3   
6 1 8

这是一个三阶幻方。每行每列以及对角线上的数字相加都相等。

下面考虑一个相反的问题。   
可不可以用 1~9 的数字填入九宫格。   
使得：每行每列每个对角线上的数字和都互不相等呢？

这应该能做到。   
比如：   
9 1 2   
8 4 3   
7 5 6

你的任务是搜索所有的三阶反幻方。并统计出一共有多少种。   
旋转或镜像算同一种。

比如：   
9 1 2   
8 4 3   
7 5 6

7 8 9   
5 4 1   
6 3 2

2 1 9   
3 4 8   
6 5 7

等都算作同一种情况。

请提交三阶反幻方一共多少种。这是一个整数，不要填写任何多余内容。

答案是：3120

下面给出解题代码：

public class 反幻方 {
    	public static int sum = 0;// 计数器
    	public static void fun(int a[], int n) {
    		if (n == 9) {
    			text(a);
    			//return;
    		} else
    			for (int i = n; i < 9; i++) {
    				{
    					int temp = a[i];
    					a[i] = a[n];
    					a[n] = temp;
    				}
    				fun(a, n + 1);
    
    				{
    					int tamp = a[i];
    					a[i] = a[n];
    					a[n] = tamp;
    				}
    			}
    	}
    
    	public static void text(int a[]) {
    		int l1 = a[0] + a[1] + a[2];
    		int l2 = a[3] + a[4] + a[5];
    		int l3 = a[6] + a[7] + a[8];
    		int s1 = a[0] + a[3] + a[6];
    		int s2 = a[1] + a[4] + a[7];
    		int s3 = a[2] + a[5] + a[8];
    		int x1 = a[0] + a[4] + a[8];
    		int x2 = a[2] + a[4] + a[6];
    		if (l1 != l2 && l1 != l3 && l1 != s1 && l1 != s2 && l1 != s3
    				&& l1 != x1 && l1 != x2)
    			if (l2 != l3 && l2 != s1 && l2 != s2 && l2 != s3 && l2 != x1
    					&& l2 != x2)
    				if (l3 != s1 && l3 != s2 && l3 != s3 && l3 != x1 && l3 != x2)
    					if (s1 != s2 && s1 != s3 && s1 != x1 && s1 != x2)
    						if (s2 != s3 && s2 != x1 && s2 != x2)
    							if (s3 != x1 && s3 != x2)
    								if (x1 != x2)
    									sum++;
    	}
    
    	public static void main(String[] args) {
    		int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    		fun(a, 0);
    		System.out.print(sum / 8);
    	}
    }

2、方格填数：使用的是上文提到的第二种方法

如下的10个格子  
                    +----+-----+----+  
                    |         |        |        |  
          +----+-----+----+-----+  
          |        |         |         |         |  
\+----+-----+-----+-----+----+  
|        |         |         |  
\+---+------+----+  
  
填入0~9的数字。要求：连续的两个数字不能相邻。  
（左右、上下、对角都算相邻）  
  
一共有多少种可能的填数方案？  
  
请填写表示方案数目的整数。  
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

下面给出解题代码：

public class 方格填数 {  
        static int count = 0;  
        public static void main(String[] args) {  
            int a[] = new int[12];  
            boolean visit[] = new boolean[10];//因为只用到了a[1]-a[10];  
            dfs(a,visit,1);  
            System.out.println(count);  
        }  
      
        private static void dfs(int[] a, boolean[] visit, int num) {  
            if (num==11) {  
                if (judge(a)) {  
                    count++;  
                }  
                return;  
            }  
            for (a[num] = 0; a[num] < 10; a[num]++) {  
                if (visit[a[num]]==false) {  
                    visit[a[num]]=true;  
                    num = num + 1;  
                    dfs(a, visit, num);  
                    num = num - 1;  
                    visit[a[num]]=false;  
                }  
            }  
        }  
      
        private static boolean judge(int[] a) {  
            if ((a[1]==a[2]+1||a[1]==a[2]-1)||  
                    (a[1]==a[6]+1||a[1]==a[6]-1)||  
                    (a[1]==a[5]+1||a[1]==a[5]-1)||  
                    (a[1]==a[4]+1||a[1]==a[4]-1)) {  
                return false;  
            }else if ((a[2]==a[5]+1||a[2]==a[5]-1)||  
                    (a[2]==a[3]+1||a[2]==a[3]-1)||  
                    (a[2]==a[7]+1||a[2]==a[7]-1)||  
                    (a[2]==a[6]+1||a[2]==a[6]-1)) {  
                return false;  
            }else if ((a[3]==a[6]+1||a[3]==a[6]-1)||  
                    (a[3]==a[7]+1||a[3]==a[7]-1)) {  
                return false;  
            }else if ((a[4]==a[5]+1||a[4]==a[5]-1)||  
                    (a[4]==a[8]+1||a[4]==a[8]-1)||  
                    (a[4]==a[9]+1||a[4]==a[9]-1)) {  
                return false;  
            }else if ((a[6]==a[7]+1||a[6]==a[7]-1)||  
                    (a[6]==a[10]+1||a[6]==a[10]-1)||  
                    (a[6]==a[9]+1||a[6]==a[9]-1)) {  
                return false;  
            }else if (a[7]==a[10]+1||a[7]==a[10]-1) {  
                return false;  
            }else if (a[8]==a[9]+1||a[8]==a[9]-1) {  
                return false;  
            }else if (a[9]==a[10]+1||a[9]==a[10]-1) {  
                return false;  
            }else if ((a[5]==a[6]+1||a[5]==a[6]-1)||  
                    (a[5]==a[10]+1||a[5]==a[10]-1)||  
                    (a[5]==a[9]+1||a[5]==a[9]-1)||  
                    (a[5]==a[8]+1||a[5]==a[8]-1)) {  
                return false;  
            }  
            return true;  
        }  
      
    }

答案是：1580  
有更好的全排列方法欢迎交流！