隨筆檔案(496)

原題如下：用1、2、2、3、4、5這六個(gè)數(shù)字，用java寫一個(gè)程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"與"5"不能相連。

解題思路：

很明顯，這是一個(gè)遞歸算法。我們可以排列將這6個(gè)數(shù)按從小到大的順序排一下，如果是1,2,3,4,5,6，那么會(huì)有1*2*3*4*5*6=6!=720個(gè)遞增的數(shù)。但如果是1,2,2,3,4,5，那么在這720個(gè)數(shù)中一定會(huì)有相同的數(shù)對(duì)出現(xiàn)（由于在這6個(gè)數(shù)中只有兩個(gè)數(shù)兩同，也就是說，如果有重復(fù)的數(shù)，那么一定是一對(duì)數(shù)，如122345會(huì)出現(xiàn)兩次）。

排列的基本規(guī)則是分步進(jìn)行。也就是說，要排列上面6個(gè)數(shù)，首先應(yīng)該選擇第一個(gè)數(shù)，這第一個(gè)數(shù)可以選擇這6個(gè)數(shù)中的任意一個(gè)，如選擇1.第二步是選擇第二個(gè)數(shù)，這第二個(gè)數(shù)不能再選擇已經(jīng)選過的數(shù)，如1.因此，它只能從后面5個(gè)數(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ù)是這個(gè)算法的核心函數(shù)。index參數(shù)表示已經(jīng)選擇過的數(shù)，用numbers數(shù)組的索引表示。如index="012"，表示numbers的前三個(gè)數(shù)已經(jīng)被選擇，也表示應(yīng)該選擇第四個(gè)數(shù)了，而這第四個(gè)數(shù)應(yīng)該從后三個(gè)數(shù)中選擇。result參數(shù)表示臨時(shí)的數(shù)字組合（這個(gè)數(shù)字組合最多是5個(gè)數(shù)字，因?yàn)椋绻搅?個(gè)數(shù)字，就表示已經(jīng)有一個(gè)結(jié)果產(chǎn)生了）。在默認(rèn)情況下index和result的值都是""。

在validate中使用了 if (s.compareTo(lastResult) <= 0)進(jìn)行判斷，由于按這種方法進(jìn)行排列，如果這6個(gè)數(shù)是遞增給出的，那么排列的結(jié)果一定是遞增的，但上述的6個(gè)數(shù)其中第2和第3個(gè)位置上都是2,因此，如果出現(xiàn)了上一個(gè)結(jié)果不小于當(dāng)前結(jié)果的情況，一定是有重復(fù)了，因此，要將這部分?jǐn)?shù)過濾出去。

使用1, 2, 2, 3, 4, 5的測試結(jié)果
122345
122543
123245
123254
123425
123452
125234
125243
125423
125432
132245
132254
132425
132452
132524
132542
142325
... ...
... ...
542313
542331
543123
543132
543213
543231
543312
543321
總數(shù)：118

使用1, 3, 3, 3, 4, 5的測試結(jié)果

133345
313345
315433
331345
331543
333145
333154
333415
333451
343315
345133
433315
451333
513334
513343
513433
541333
543133
543313
543331
總數(shù)：20