递归实现数学排列
递归，还是回溯？选择了递归，记得回溯算法，以前课程设计做的一个迷宫程序涉及到。
?
?
/* * To change this template, choose Tools | Templates * and open the template in the editor. */package com.xiva.baseKnowledge;import java.util.Arrays;import java.util.LinkedHashSet;import java.util.Set;/** * @Description "4"不能在第三位，"3"与"5"不能相连 * @author XIVA */public class Arrangement { //static int numArray[] = {1, 2, 2, 3, 4, 5}; static int numArray[] = {1, 2, 2, 3, 4, 5}; //static int[] result = {0,0,0,0,0,0}; static int[] result = new int[numArray.length]; static int index = 0; static int count = 0; static boolean isOut = false; static Set arraySet = new LinkedHashSet();//存储 public static int getArrangement(int array[]){ boolean checkOut = true; if(array.length < 1){ //System.out.print("Start:"); for(int j = 0; j < result.length; j++){ //System.out.print(result[j]); //业务判断过滤 if(result[j] == 4 && j == 3){ checkOut = false; } if( result[j] == 3){ if((j>0 && result[j-1] == 5) || (j < result.length - 1 && result[j + 1] == 5)){ checkOut = false; } } } //System.out.println(""); isOut = true; String reStr = Arrays.toString(result); //arraySet.contains(reStr)可以不需要判断 if(arraySet.contains(reStr) || !checkOut){ System.out.println(reStr); }else{ arraySet.add(reStr); } count = count + 1; return 1; } for(int i = 0; i < array.length; i ++){ //此处还可以简化 int[] headArray = Arrays.copyOfRange(array, 0, i); int[] footArray = Arrays.copyOfRange(array, i + 1, array.length); int[] newArray = new int[headArray.length + footArray.length]; //数组复制 System.arraycopy(headArray, 0, newArray, 0, headArray.length); System.arraycopy(footArray, 0, newArray, headArray.length, footArray.length); if( isOut){ index = numArray.length - array.length; isOut = false; } result[index] = array[i]; index = index + 1; //if( newArray.length > 0) //递归调用 getArrangement(newArray); } return 0; } public static void main(String[] args){ getArrangement(numArray); System.out.println(count); System.out.println(arraySet.size()); } }?
?最终，set中存放的是类似于“[5, 4, 3, 2, 2, 1]” 的字符串。这样即使使用10以上的数进行排列，也保证了数据的正确性。
?
本题目中未加入过滤是的结果个数应该是：6!/2!
?
当然这个排列算法只考虑了排列的一种情况那就是全排列。