全排列輸出（遞歸實現）

2019 年 10 月 4 日
筆記

全排列是一種比較常用的演算法。本文給出遞歸實現的兩個方法。

一、方法一

1.1 思想

處理遞歸的時候，採用兩個字元串變數，一個存放固定前綴，一個存放剩下的待處理的字元串。如：

@param prefix 固定前綴@param valueToProcess 待處理的字元串

固定前綴prefix的初始值為空值「」，隨著遞歸的進行不斷變化；剩下的待處理元素，會隨著遞歸的進行不斷減少。

何時輸出一個結果？

當剩下的待處理的字元串只有一個元素的時候，直接輸出其中一個結果。格式為：固定前綴 + 待處理的一個元素

    private void permuteRecusion(String prefix, String valueToProcess) {        int len = valueToProcess.length();        if (len == 1) {            System.out.println(prefix + valueToProcess);            return;        }        //省略其餘部分    }

依次從剩下待處理字元元素中，選擇一個元素（比如A）與固定前綴組成一個新的固定前綴，然後與新的不包含選中元素（比如A）的待處理字元串元素一道，繼續調用遞歸函數。
直到剩下的待處理元素只有一個元素時，將固定前綴和該唯一待處理的元素一道輸出。

舉個例子，假設要輸出ABC的全排列，採用上述思想，輸出全排列的過程如下：

第一步：

待處理的字元串為ABC，固定前綴為空 ""

依次從ABC中選取元素，然後與前綴組成新的前綴，有如下三種情況：

A BC , B AC , C AB （註：綠色背景的為固定前綴，黃色背景的待處理的字元串元素）

第二步：

第一步中的三個結果，繼續調用遞歸函數，以A BC 為例，

依次從BC中選取元素，然後與前綴（A）組成新的前綴，有如下兩種情況：

A BC , A CB

同理，我們可以獲取B AC 和C AB 的結果，與A BC 的結果一共產生六個結果，包括：

A BC , A CB B AC , B CA C AB , C BA

第三步：

第二步產生的六個結果，繼續進行。因為剩下的待處理的字元串元素只有一個，所以直接輸出即可。格式為固定前綴+待處理的字元串元素。也就得到ABC的全排列結果：

ABCACBBACBCACABCBA

根據上述思想，我們就能很容易地寫出遞歸方法了，如：

/** * @author wangmengjun * */public class Permutation {      /**     * 根據指定的字元串，輸入全排列     *      * @param value     *            用於全排列的指定字元串     */    public void permutation(String value) {        if (null == value || value.length() == 0) {            throw new IllegalArgumentException("value不能為空");        }        permuteRecusion("", value);    }      /**     * 遞歸處理     *      * @param prefix 固定前綴     * @param valueToProcess 待處理的字元串     */    private void permuteRecusion(String prefix, String valueToProcess) {        int len = valueToProcess.length();        if (len == 1) {            System.out.println(prefix + valueToProcess);            return;        }        for (int i = 0; i < len; i++) {            permuteRecusion(prefix + valueToProcess.charAt(i), valueToProcess.substring(0, i)                    + valueToProcess.substring(i + 1, len));        }    }    }

測試程式碼

/** * @author wangmengjun * */public class Main {      public static void main(String[] args) {        Permutation example = new Permutation();        System.out.println("AB的全排列:");        example.permutation("AB");                System.out.println("ABC的全排列:");        example.permutation("ABC");    }  }

輸出結果

AB的全排列:ABBAABC的全排列:ABCACBBACBCACABCBA

1.2 程式碼調整

在上述遞歸程式碼中，從待處理字元串元素中選出一個元素和固定前綴時，為了得到不包含該選中元素的新的待處理字元串元素，程式碼採用了字元串substring方法來做。

valueToProcess.substring(0, i)  + valueToProcess.substring(i + 1, len)

在遞歸中，上述substring太過頻繁，不喜歡。我們寫一個新的函數，效果與上述substring操作等效。程式碼如下：

    /**     * 返回一個不包含指定下標元素的字元串     * @param i 需要移除元素的下標     * @param valueToProcess 用於處理的字元串     * @return     */    private String populateCandidateValue(int i, String valueToProcess) {        int len = valueToProcess.length();        char[] sourceValue = valueToProcess.toCharArray();        char[] destValue = new char[len - 1];        System.arraycopy(sourceValue, 0, destValue, 0, i);        System.arraycopy(sourceValue, i + 1, destValue, i, destValue.length - i);        return new String(destValue);      }

將permuteRecusion方法中的substring程式碼段替換掉。

    /**     * 遞歸處理     *      * @param prefix 固定前綴     * @param valueToProcess 待處理的字元串     */    private void permuteRecusion(String prefix, String valueToProcess) {        int len = valueToProcess.length();        if (len == 1) {            System.out.println(prefix + valueToProcess);            return;        }        for (int i = 0; i < len; i++) {            permuteRecusion(prefix + valueToProcess.charAt(i),                    populateCandidateValue(i, valueToProcess));        }    }

將上述改動，存放在一個新的文件Permutation2.java中。

/** * @author wangmengjun * */public class Permutation2 {      /**     * 根據指定的字元串，輸入全排列     *      * @param value     *            用於全排列的指定字元串     */    public void permutation(String value) {        if (null == value || value.length() == 0) {            throw new IllegalArgumentException("value不能為空");        }        permuteRecusion("", value);    }      /**     * 遞歸處理     *      * @param prefix 固定前綴     * @param valueToProcess 待處理的字元串     */    private void permuteRecusion(String prefix, String valueToProcess) {        int len = valueToProcess.length();        if (len == 1) {            System.out.println(prefix + valueToProcess);            return;        }        for (int i = 0; i < len; i++) {            permuteRecusion(prefix + valueToProcess.charAt(i),                    populateCandidateValue(i, valueToProcess));        }    }      /**     * 返回一個不包含指定下標元素的字元串     * @param i 需要移除元素的下標     * @param valueToProcess 用於處理的字元串     * @return     */    private String populateCandidateValue(int i, String valueToProcess) {        int len = valueToProcess.length();        char[] sourceValue = valueToProcess.toCharArray();        char[] destValue = new char[len - 1];        System.arraycopy(sourceValue, 0, destValue, 0, i);        System.arraycopy(sourceValue, i + 1, destValue, i, destValue.length - i);        return new String(destValue);      }  }

在Permutation2.java中，我們增加了一個函數，用於返回一個不包含指定下標元素的字元串。在這個方法中，我們先將源字元串轉換成char數組，然後通過數組複製，返回時，又將目標char數組，轉換成String來處理。 還是不喜歡，直接使用char[]數組不就可以了嗎？

接下來，我們再來做一些調整，將待處理的字元串，從String改成char[]。修改後的程式碼如下，存放在Permutation3.java中，

/** * @author wangmengjun * */public class Permutation3 {      /**     * 根據指定的字元串，輸入全排列     *      * @param value     *            用於全排列的指定字元串     */    public void permutation(String value) {        if (null == value || value.length() == 0) {            throw new IllegalArgumentException("value不能為空");        }        permuteRecusion("", value.toCharArray());    }      /**     * 遞歸處理     *      * @param prefix 固定前綴     * @param valueToProcess 待處理的字元串     */    private void permuteRecusion(String prefix, char[] valueToProcess) {        int len = valueToProcess.length;        if (len == 1) {            System.out.println(prefix + valueToProcess[0]);            return;        }        for (int i = 0; i < len; i++) {            permuteRecusion(prefix + valueToProcess[i], populateCandidateValue(i, valueToProcess));        }    }      /**     * 返回一個不包含指定下標元素的字元串     * @param i 需要移除元素的下標     * @param valueToProcess 用於處理的字元串     * @return     */    private char[] populateCandidateValue(int i, char[] sourceValue) {        int len = sourceValue.length;        char[] destValue = new char[len - 1];        System.arraycopy(sourceValue, 0, destValue, 0, i);        System.arraycopy(sourceValue, i + 1, destValue, i, destValue.length - i);        return destValue;      }  }

至此，方法一的實現就全部結束了。

二、方法二（採用交換的演算法）

2.1 思想

方法二的思想是採用交換的演算法，思想來源於GeeksforGeeks.org. 網站

ABC全排列的過程如下圖所示：

根據上述思想，編寫程式碼如下：

/** *  * @author wangmengjun * */public class Permute {      public void permute(String value) {        if (StringUtils.isEmpty(value)) {            throw new IllegalArgumentException("內容不能為空");        }          int len = value.length();        permuteRecusion(value.toCharArray(), 0, len - 1);    }      private void permuteRecusion(char[] charValues, int begin, int end) {        if (begin == end) {            System.out.println(Arrays.toString(charValues));            return;        }        for (int i = begin; i <= end; i++) {            swap(charValues, begin, i);            permuteRecusion(charValues, begin + 1, end);            swap(charValues, begin, i);        }    }      private void swap(char[] charValues, int i, int j) {        char temp = charValues[i];        charValues[i] = charValues[j];        charValues[j] = temp;    }}

三、小結

本篇博文給出了兩個遞歸實現全排列輸出的方法。其中，

方法一給出了思想，程式碼實現、以及對程式碼的部分優化，也算是一個不錯的編寫程式碼的旅程。

方法二，如大家有興趣，可以參考上述給出的連接，查看更詳細的內容。在

本篇博文中就不詳細展開講了，有思路了，編寫程式碼就簡單了。

方法二中，使用交換的思想，維持一個char數組，其他通過變換來做。相對方法一，減少了很多數組拷貝或者String對象創建等，相比方法一來講更好。方法一的優勢在於比較好理解。

註：如上兩種方法適合沒有重複元素的結果，如果有重複元素，還得添加額外的判斷條件進行過濾。

全排列輸出遞歸實現就寫到這裡，後期會找時間將非遞歸的實現寫上去。

如大家有較好的方法，也請告訴我一下，相互交流、相互進步~~~