題目

輸入一個字符串，打印該字符中字符的所有排列。

例如，輸入字符串abc，則打印出由字符a、b、c所能排列出來的所有字符串有abc、acb、bac、bca、cab、cba

分析

把一個字符串看成由兩部分組成：第一部分是它的第一個字符；第二部分是后面的所有字符。

求整個字符串的排列，可以看成兩步：

1. 求所有可能出現在第一位置，即把第一個字符和后面所有的字符交換。
2. 固定第一個字符，求后面所有的排列（遞歸套用，將后面所有字符分成兩部分：后面字符的第一個字符，以及這個字符之后的所有字符，回到步驟1。遞歸結束條件：后面字符的數量為1）。

放碼

import java.util.ArrayList;
import java.util.List;import com.lun.util.MyUtils;public class CharsPermutation {public List<String> permute(String src) {List<String> list = new ArrayList<>();if(!MyUtils.checkStringEmpty(src))permute(list, "", src.toCharArray(), 0);return list;}private void permute(List<String> list, String mid, char[] src, int index) {if(index == src.length) {list.add(mid.toString());}else {for(int i = index; i < src.length; i++) {swap(src, i , index);permute(list, mid + src[index], src, index + 1);swap(src, i , index);}}}private void swap(char[] src, int i, int j) {char temp = src[i];src[i] = src[j];src[j] = temp;}}

測試

import static org.hamcrest.Matchers.*;
import static org.junit.Assert.*;import java.util.List;
import org.junit.Test;public class CharsPermutationTest {@Testpublic void testPermute() {CharsPermutation cp = new CharsPermutation();List<String> list = cp.permute("abc");//System.out.println(list);assertThat(list, containsInAnyOrder("abc","acb","bac","bca","cba","cab"));}}