原題如下：用1、2、2、3、4、5這六個數(shù)字，用java寫一個程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"與"5"不能相連。
解題思路：
很明顯，這是一個遞歸算法。我們可以排列將這6個數(shù)按從小到大的順序排一下，如果是1,2,3,4,5,6，那么會有1*2*3*4*5*6= 6!=720個遞增的數(shù)。但如果是1,2,2,3,4,5，那么在這720個數(shù)中一定會有相同的數(shù)對出現(xiàn)（由于在這6個數(shù)中只有兩個數(shù)兩同，也就是說，如果有重復(fù)的數(shù)，那么一定是一對數(shù)，如122345會出現(xiàn)兩次）。
排列的基本規(guī)則是分步進行。也就是說，要排列上面6個數(shù)，首先應(yīng)該選擇第一個數(shù)，這第一個數(shù)可以選擇這6個數(shù)中的任意一個，如選擇1.第二步是選擇第二個數(shù)，這第二個數(shù)不能再選擇已經(jīng)選過的數(shù)，如1.因此，它只能從后面5個數(shù)中選擇。如選擇2。以此類推。
我們也可以在程序中模擬這一過程。源程序如下：
public class test1
{
private int[] numbers = new int[]
{ 1, 2, 3, 3, 4, 5 };
public int n;
private String lastResult = "";
private boolean validate(String s)
{
if (s.compareTo(lastResult) <= 0)
return false;
if (s.charAt(2) == '4')
return false;
if (s.indexOf("35") >= 0 || s.indexOf("53") >= 0)
return false;
return true;
}
public void list(String index, String result)
{
for (int i = 0; i < numbers.length; i++)
{
if (index.indexOf(i + 48) < 0)
{
String s = result + String.valueOf(numbers[i]);
if (s.length() == numbers.length)
{
if (validate(s))
{
System.out.println(s);
lastResult = s;
n++;
}
break;
}
list(index + String.valueOf(i), s);
}
}
}
public static void main(String[] args)
{
test1 t = new test1();
t.list("", "");
System.out.println("總數(shù)：" + t.n);
}
}
其中l(wèi)ist函數(shù)是這個算法的核心函數(shù)。index參數(shù)表示已經(jīng)選擇過的數(shù)，用numbers數(shù)組的索引表示。如index="012"，表示numbers的前三個數(shù)已經(jīng)被選擇，也表示應(yīng)該選擇第四個數(shù)了，而這第四個數(shù)應(yīng)該從后三個數(shù)中選擇。result參數(shù)表示臨時的數(shù)字組合（這個數(shù)字組合最多是5個數(shù)字，因為，如果到了6個數(shù)字，就表示已經(jīng)有一個結(jié)果產(chǎn)生了）。在默認情況下index和result的值都是""。
在validate中使用了 if (s.compareTo(lastResult) <= 0)進行判斷，由于按這種方法進行排列，如果這6個數(shù)是遞增給出的，那么排列的結(jié)果一定是遞增的，但上述的6個數(shù)其中第2和第3個位置上都是2,因此，如果出現(xiàn)了上一個結(jié)果不小于當(dāng)前結(jié)果的情況，一定是有重復(fù)了，因此，要將這部分數(shù)過濾出去。
index保存了當(dāng)前數(shù)字串的索引，index.indexOf(i + 48) < 0就是判斷當(dāng)前的數(shù)字的索引是否在index中（由于給定的數(shù)字串有重復(fù)的數(shù)字，因此，只能使用索引來判斷了），如果不在，就會認為這個數(shù)字還沒有加到index中，如果存在了，說明這個數(shù)已經(jīng)在數(shù)字串中了。當(dāng)i=0的時候，i+48是0的ASCII，因為你index中存的畢竟是索引，是位置嘛，所以是從0開始的