P154、面试题28：字符串的排列

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab、cba。

测试用例：

1）功能测试（输入的字符串中有1个或者多个字符）；

2）特殊输入测试（输入的字符串的内容为空或者是null指针）；

相关题目：

1）如果不是求字符的所有排列，而是求字符的所有组合，该怎么办。还是输入三个字符a、b、c，则它们的组合有a、b、c、ab、ac、bc、abc。当交换字符串中的两个字符时，虽然能得到两个不同的排列，但却是同一个组合。比如ab和ba是不同的排列，但只算一个组合。

2)输入一个含有8个数字的数组，判断有没有可能把这8个数字分别放到正方体的8个顶点上，使得正方体上三组相对的面上的4个顶点的和都相等。

3）在8*8的国际象棋上摆放8个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角线上。

思路：还是万年不变的递归！！！需要通过Debug来了解递归思想了。

代码实现：

package com.yyq;
import java.util.Arrays;
/**
 * Created by Administrator on 2015/9/20.
 */
public class StringPermutation {
    public static void permutation_1(char[] pStr){
        if (pStr == null || pStr.length == 0)
            return;
        permutation_2(pStr, 0,pStr.length-1);
    }
    public static void permutation_2(char[] buf, int start, int end) {
        if (start == end) {// 当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可
            for (int i = 0; i <= end; i++) {
                System.out.print(buf[i]);
            }
            System.out.println();
        } else {// 多个字母全排列
            for (int i = start; i <= end; i++) {
                char temp = buf[start];// 交换数组第一个元素与后续的元素
                buf[start] = buf[i];
                buf[i] = temp;
                permutation_2(buf, start + 1, end);// 后续元素递归全排列
                temp = buf[start];// 将交换后的数组还原
                buf[start] = buf[i];
                buf[i] = temp;
            }
        }
    }
    // ====================测试代码====================
    public static void Test(char[] pStr)
    {
        if(pStr == null)
            System.out.println("Test for NULL begins:");
        else
            System.out.println("Test for " + Arrays.toString(pStr) + " begins:");
        permutation_1(pStr);
        System.out.println();
    }
    public static void main(String[] args){
        Test(null);
        String string01 = "";
        char string1[] = string01.toCharArray();
        Test(string1);
        String string02 = "a";
        char string2[] = string02.toCharArray();
        Test(string2);
        String string03 = "ab";
        char string3[] = string03.toCharArray();
        Test(string3);
        String string04 = "abc";
        char string4[] = string04.toCharArray();
        Test(string4);
    }
}

结果输出：

Test for NULL begins:

Test for [] begins:

Test for [a] begins:

Test for [a, b] begins:

Test for [a, b, c] begins:

abc

acb

bac

bca

cba

cab