字符串全排列的非递归/递归算法

声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
给定一个字符串，求一个字符串的全排列组合
起点：字典序最小的排列，例如12345
终点：字典序最大的排列，例如54321
过程：从当前排列生成字典序列刚好比它大的下一个排列
如：21453的下一个排列是23145
解题步骤：
1、给定一个字符串S[N], 从字符串从后往找中最后一个升序的位置即S[k]>Sk+1, S[i]<S[i+1];
2、在S[i+1...N-1]中比Ai大的最小值Sj
3、交换：Si, Sj;
4、翻转：S[i+1...N-1]
Java版本非递归算法如下:

package com.mystudy.algorithm;
/**
 * 字符串全排列的非递归算法,找到下一个比本身大的字符串
 *
 */
public class GetNextPermutation {

    public static void main(String[] args) {
        int[] arr = {1,4,2,5};
        print(arr);
        System.out.println("nextPermutation is : ");
        while(getNextPermutation(arr, arr.length)){
            print(arr);
        }
    }
    /**
     * 把一个数组从from到to做反转
     * @param arr
     * @param from
     * @param to
     */
    public static void reverse(int arr[], int from, int to){
        int t;
        while(from < to){
            t = arr[from];
            arr[from] = arr[to];
            arr[to] = t;
            from++;
            to--;
        }
    }

    public static boolean getNextPermutation(int[] arr, int size) {
        int i = size-2;//后找
        while(i>=0 && arr[i]>=arr[i+1]){
            i--;
        }
        if (i<0) {
            return false;
        }
        //小大
        int j = size - 1;
        while(arr[j] <= arr[i]){
            j--;
        }
        //交换
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        
        //反转
        reverse(arr,i+1,size-1);
        return true;
    }
    
    public static void print(int arr[]){
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
}

Java版本递归算法如下：

package com.mystudy.algorithm;

/**
 * 求字符串的全排列
 * 递归的思想
 * 比如  abcde  先求出abcd的全排列，然后将e分别插入全排列的5个位置
 * a 全排列  a
 * ab 全排列  ab ba
 * abd 全排列即是  cab acb abc cba bca bac
 *
 */
public class Permutation {
    public static void main(String[] args) {
        int a[] = {1,3,3,4};
        permutation1(a, 0);
    }
    
    public static void print(int[] a){
        for (int i : a) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    /**
     * 一个字符串的全排列递归算法,时间复杂度O((n+1)!)
     * @param a
     * @param n
     */
    public static void permutation(int a[], int n){
        if (n == a.length - 1) {
            print(a);
            return;
        }
        for(int i = n; i < a.length; i++){
            int temp = a[i];//交换a[i],a[n]
            a[i] = a[n];
            a[n] = temp;
            permutation(a, n+1);
            temp = a[i];//交换a[i],a[n]
            a[i] = a[n];
            a[n] = temp;
        }
    }
    /**
     * 判断一个数字是否在数组中
     * @param a
     * @param n
     * @param t
     * @return
     */
    public static boolean isDuplicate(int[] a, int n, int t){
        while(n < t){
            if (a[n] == a[t]) {
                return false;
            }
            n++;
        }
        return true;
    }
    /**
     * 去除重复元素的全排列
     * @param a
     * @param n
     */
    public static void permutation1(int a[], int n){
        if (n == a.length - 1) {
            print(a);
            return;
        }
        for(int i = n; i < a.length; i++){
            if (!isDuplicate(a, n, i)) {//a[i]是否与[n,i)重复
                continue;
            }
            int temp = a[i];//交换a[i],a[n]
            a[i] = a[n];
            a[n] = temp;
            permutation1(a, n+1);
            temp = a[i];//交换a[i],a[n]
            a[i] = a[n];
            a[n] = temp;
        }
    }
}

去除重复的排列的结果：
1 3 3 4
1 3 4 3
1 4 3 3
3 1 3 4
3 1 4 3
3 3 1 4
3 3 4 1
3 4 3 1
3 4 1 3
4 3 3 1
4 3 1 3
4 1 3 3
不去重复的排列结果：
1 3 3 4
1 3 4 3
1 3 3 4
1 3 4 3
1 4 3 3
1 4 3 3
3 1 3 4
3 1 4 3
3 3 1 4
3 3 4 1
3 4 3 1
3 4 1 3
3 3 1 4
3 3 4 1
3 1 3 4
3 1 4 3
3 4 1 3
3 4 3 1
4 3 3 1
4 3 1 3
4 3 3 1
4 3 1 3
4 1 3 3
4 1 3 3