前言
近日看到一个很有趣味的编程题，激起了鄙人强烈的研究欲望。在解答该问题的同时，发现了采用递归来计算排列的方法，现将方法和程序代码公布，欢迎广大算法爱好者前来阅读和交流。
原问题
有2N(3<N<40)个木块，并对之编号为1-N，当然，同一编号需要在两个木块中出现。然后将这些木块这样排序，编号为n的木块间需要间隔n个位置。为了便于把问题说清楚，举例说明。例如当N=3时，将得到入下排序3、1、2、1、3、2；当Ｎ＝４时，输出4、1、3、1、2、4、3、2；当N=5时，没有找到符合条件的排列。
请编写程序能够找出任意输入4<N<40的一种可行排列。
编程思想
当我看到这个问题时，首先想到的解决方案是先把所有的排列找出来，存入集合。然后从集合中遍历出所有排列，依次计算该排列是否符合要求。
如何找出一组数字的所有排列，是最棘手的问题。我的方法是先定义两个数组A和B，A数组的下标用来表示第几个位置，数组中元素的值表示该位置放置的数字是多少。B数组的下标表示这些数字，1、1、2、2…，数组中元素的值表示数字是否已经被放置。采用循环遍历B数组，如果发现未被放置的数字就放置在A数组中，即将B数组中元素的下标赋值给A数组中元素，以此来模拟一次排列的过程。一次放置结束后，采用递归的方法，进入下一个位置后再次遍历B数组，发现未被取出的数字则依次取出后放置到该位置中。直到把所有位置均放置入数字，不再进行递归，并收集排列存入集合。
待将所有排列收集进一个集合后，遍历集合，依次取出数组。取出一个数组后，从1开始循环计算当前数字在数组中的两个位置，再判断两个位置间隔是否等于数字本身，相等则符合条件。如果所有数字均符合条件，说明这个排列是我们需要的。
算法
1、定义一维数组position，数组的下标用来表示第几个位置，数组中元素的值表示该位置放置的数字是多少。
2、定义二维数组array，数组的下标表示这些数字，1、1、2、2…，数组中元素的值表示数字是否已经被放置。
3、定义变量i，表示位置。
3、为position数组赋初始值为0，当position[i]=0时表示该位置尚未被放入数字。为array数组赋初始值，当array[i][j]=0时，表示该数字尚未被放入位置中。
4、从第1个位置开始，在每个位置都要采用循环遍历arry数组，找到未被放置的数字依次放置到该位置中。
5、找到未被放置的数字时将array数组中元素值设置为0表示该数字已经被取出放置。
6、i自增1，表示进入下一个位置。
7、如果i的值等于数字的数量，说明放置完成，将得到的排列存入集合。否则通过递归的方式找出第下一个位置可以放置的数字进行放置。
8、收集完所有排列后，遍历集合中的所有收集到的排列。
9、定义变量a表示某排列中位置符合条件的数字的数量（两个数字的间隔等于数字本身这个条件）。
10、从1开始，直到输入的数字为止。求该数字在排列中的两个位置，如果两个位置间距等于数字本身，则说明该数字的位置符合要求，将a自增1。
11、如果上一步结束后a的数字等于最初输入的数组number，说明该排列里面所有的数字位置都符合要求，是符合条件的排列。
12、采用循环遍历的方式展示符合条件的排列。
程序代码
public class Arrange {
//定义集合，用来存储排列
List list=new ArrayList();
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("请输入一个数字");
Scanner input = new Scanner(System.in);
int number = input.nextInt();
//定义一维数组，数组的下标用来表示第几个位置，数组中元素的值表示该位置放置的数字是多少
int[] position=new int[number*2];
//定义二维数组，数组的下标表示这些数字，1、1、2、2....，数组中元素的值表示数字是否已经被放置
int[][] array = new int[number][2];
//为position数组赋初始值为0，当position[i]=0时表示该位置尚未被放入数字
for(int i=0;i<number*2;i++){
position[i]=0;
}
//为array数组赋初始值，当array[i][j]=0时，表示该数字尚未被放入位置中
for(int i=0;i<number;i++){
array[i][0]=1;
array[i][1]=1;
}
System.out.println("赋值完毕");
Arrange arrange=new Arrange();
//初始位置为0
int x=0;
//调用capture方法，收集所有排列，capture方法为本类中的核心方法，写在本程序的下面
arrange.capture(position, array, number,x);
System.out.println("已经收集所有排列，正在检查哪些符合条件");
//遍历集合中的所有收集到的排列
for(int m=0;m<arrange.list.size();m++){
int[] result=(int[]) arrange.list.get(m);
//定义变量a2表示某排列中符合条件的数字的数量（两个数字的间隔等于数字本身这个条件）
int a2=0;
//从1开始，求该数字在排列中的两个位置
for(int x1=1;x1<=number;x1++){
//定义数组a1，用来存储某数字在排列中的位置
int[]a1=new int[2];
int x3=0;
//遍历数组，找出某个数字在排列中的两个位置
for(int x2=0;x2<result.length;x2++){
if(result[x2]==x1){
//找到位置，将位置数字存储进a1数组
a1[x3]=x2+1;
x3++;
}
}
//求两个位置中间的间隔
int a=a1[1]-a1[0]-1;
//如果间隔不等于数字本身，则说明部分和条件，结束本轮循环
if(a!=x1){
break;
}else{
//如果相等，说明该数字的位置符合要求，a2自增
a2++;
}
}
//当a2==number，说明排列中的每个数字都符合要求，即找到了需要的排列
if(a2==number){
System.out.print("已经找到这样的排列：");
//展示程序计算的结果
for(int i6=0;i6<result.length;i6++){
System.out.print(result[i6]);
}
System.out.println();
}
}
}
public void capture(int[]position,int[][]array,int number,int i){
//从第1个位置开始，在每个位置都要遍历arry数组，找到未被放置的数字依次放置
//这个for循环表示在第x个位置分别放1，2，3....
for(int j=0;j<number;j++){
//当数组元素的值为初始值1时，表示这个数字未被放置
if(array[j][0]==1){
//定义一个新数组，将原数组的值全部赋给它，避免原数组值在递归中被改变影响接下来的循环
int[]positionChild=position.clone();
//将被放置数字的位置赋给positionChild数组中的元素
positionChild[i]=j+1;
//定义一个新数组，将原数组的值全部赋给它，避免原数组值在递归中被改变影响接下来的循环
int[][]arrayChild=new int[number][2];
for(int i2=0;i2<array.length;i2++){
arrayChild[i2][0]=array[i2][0];
arrayChild[i2][1]=array[i2][1];
}
//arrayChild[j][0]值设置为0表示该数字已经被取出放置
arrayChild[j][0]=0;
//接下来要进入下一个位置放置数字
int i1=i+1;
//如果位置的数已经等于number，说明数字放置完成
if(i1==number*2){
//将得到的排列存入集合
list.add(positionChild);
}else{
//如果尚未放置全部数字，通过递归的方式确定第下一个位置可以放置的数字
this.capture(positionChild, arrayChild, number,i1);
}
}
if(array[j][1]==1){
int[]positionChild=position.clone();
positionChild[i]=j+1;
int i1=i+1;
int[][]arrayChild=new int[number][2];
for(int i2=0;i2<array.length;i2++){
arrayChild[i2][0]=array[i2][0];
arrayChild[i2][1]=array[i2][1];
}
arrayChild[j][1]=0;
if(i1==number*2){
list.add(positionChild);
}else{
this.capture(positionChild, arrayChild, number,i1);
}
}
}
}
}
总结
该问题的核心是如何一个程序计算一个数字组合（或其他组合）的所有排列，鄙人在解决此问题中想到的方法是采用循环加递归。从第1个位置开始，在每个位置中均使用循环来遍历数字组合，若发现没有被排序的数字则将依次其放入该位置中。每次放置后，检查当前位置是否是最后一个位置。不是的话则进入下一个位置，采用递归的方法重新遍历数字组合，若发现没有被排序的数字则将依次其放入该位置中……直到当前位置是最后一个位置时，待数字放置结束后将排列存入集合。
下面的代码采用递归的方法实现简单的求一组数字的所有排列并展示：
public class SimpleArrange {
List list=new ArrayList();
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("请输入一个数字");
Scanner input = new Scanner(System.in);
int number = input.nextInt();
//定义一个位置数组，数组的下标用来表示第几个位置，数组中元素的值表示该位置放置的值是多少
int[] position=new int[number];
//定义一个数组，数组的下标表示这些数字，1、1、2、2....，数组中元素的值表示数字是否已经被放置
int[]array = new int[number];
//为数组赋初始值，初始值1 表示位置尚未被放置进数字，数字尚未放置进某位置
for(int i=0;i<number;i++){
position[i]=1;
array[i]=1;
}
SimpleArrange A1=new SimpleArrange();
//定义初始位置，因为数组的下标从0开始，所有初始位置我也从0开始
int i=0;
//调用方法得到所有排列的集合，本方法是程序的核心，方法体见程序的下半部分
A1.capture(position, position, number,i);
//展示收集到的所有排列
for(int m=0;m<A1.list.size();m++){
int[] result=(int[]) A1.list.get(m);
for(int n=0;n<result.length;n++){
System.out.print(result[n]);
}
System.out.println("-------------");
}
}
//先从检查第一个位置开始，在第1个位置中遍历数组。传入的参数i表示位置，值为1。
public void capture(int[] position,int[]array,int number,int i){
//遍历存储数字的数组，查看当前位置可以放置的数字有哪些，然后逐一放置
for(int j=0;j<number;j++){
//如果数组的元素的值为1，表示该元素表示的数字尚未被放置
if(array[j]==1){
//复制数组，避免递归中改变原数组的值影响下一次循环
int[]positionChild=position.clone();
int[]arrayChild=array.clone();
//在当前位置上放置数字
positionChild[i]=j+1;
//表示该数字已经被取出
arrayChild[j]=0;
//进入下一个位置
int i1=i+1;
//如果位置的数值是number，说明位置已被填满
if(i1==number){
//得到的排列存入集合
list.add(positionChild);
}else{
//通过递归的方式确定第下一个位置可以放置的数字
this.capture(positionChild, arrayChild, number,i1);
}
}
}
}
}
用递归计算数学排列题示例
我从网上找了一个数学上的排列题（高中数学），相信高中数学成绩好的同学都会用数学的方法来做。下面我采用递归算法来编写程序计算排列题。
题目：有6道选择题,答案分别为A 、B 、C 、D 、D 、D ,在安排题目顺序时,要求三道选D 的题目任意两道不能相邻,则不同的排序方法有哪些？
这道题编程的话基本步骤和方法和我以上写的两个程序相同，但是因为有限制条件，所以需要加入判断语句来得出符合限定条件的结果即可。
步骤和程序代码：
public class ArrangeQuestion {
List list=new ArrayList();
public static void main(String[] args) {
// TODO Auto-generated method stub
int number = 6;
//定义一个位置数组，数组的下标用来表示第几个位置，数组中元素的值表示该位置放置的值是多少
char[] position=new char[number];
//定义一个数组，表示需要排序的字母
char[]array = {'A','B','C','D','D','D'};
ArrangeQuestion A1=new ArrangeQuestion();
//定义初始位置，因为数组的下标从0开始，所有初始位置我也从0开始
int i=0;
//调用方法得到所有排列的集合，本方法是程序的核心，方法体见程序的下半部分
A1.capture(position, array, number,i);
//展示收集到的所有排列
for(int m=0;m<A1.list.size();m++){
char[] result=(char[]) A1.list.get(m);
for(int n=0;n<result.length;n++){
System.out.print(result[n]);
}
System.out.println("-------------");
}
}
//先从检查第一个位置开始，在第1个位置中遍历数组。传入的参数i表示位置，值为1。
public void capture(char[] position,char[]array,int number,int i){
//遍历存储数字的数组，查看当前位置可以放置的数字有哪些，然后逐一放置
for(int j=0;j<number;j++){
//如果数组的元素不为X，表示该元素表示的数字尚未被放置
if(array[j]!='X'){
//复制数组，避免递归中改变原数组的值影响下一次循环
char[]positionChild=position.clone();
char[]arrayChild=array.clone();
//在当前位置上放置字母
positionChild[i]=array[j];
//表示该数字已经被取出
arrayChild[j]='X';
//到第二为位置时，需要判断前后两个位置的字母是否相同
//注意数组的下标从0开始，所有1表示第二个位置
if(i>0){
if(positionChild[i-1]!=positionChild[i]){
//进入下一个位置
int i1=i+1;
//如果位置的数值是number，说明位置已被填满
if(i1==number){
//得到的排列存入集合
list.add(positionChild);
}else{
//通过递归的方式确定第下一个位置可以放置的数字
this.capture(positionChild, arrayChild, number,i1);
}
}
}else{
int i1=i+1;
this.capture(positionChild, arrayChild, number,i1);
}
}
}
}
}
![查找算法之二分查找查找算法之二分查找[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)