几种全排列算法

0.字典序法 参考https://blog.csdn.net/babynumber/article/details/42706757 在O(n)的时间复杂度下生成当前排列的下一个排列（字典序）。 详细算法去读上面的博客。 简单的讲：

1、从右向左找到第一个正序对（array[i] < array[i+1]，因为没有等号，所以可以完美去掉重复的排列）

2、从i开始向右搜索，找到比array[i]大的字符中最小的那个，记为array[j]

3、交换array[i]和array[j]

4、将i后面的字符反转

这就得到了字典序的下一个排列。 连续使用这个方法则可从字典序最小的排列推出全部排列。 时间复杂度O(n*n!)

import java.util.*;
public class Solution {
    public ArrayList<string> Permutation(String str) {
        ArrayList<string> res = new ArrayList<string>();
        if(str.length() == 0) return res;
        char [] array = str.toCharArray();
        Arrays.sort(array);
        String s = new String(array);
        res.add(str);
        while(true){
            s = nextString(s);
            if(!s.equals("finish")){
                res.add(s);
            }
            else{
                break;
            }
        }
        return res;
    }
    
    public String nextString(String str){
        char [] array = str.toCharArray();
        int length = str.length();
        int i = length-2;
        for(; i&gt;=0 &amp;&amp; array[i] &gt;= array[i+1]; i--);
        if(i == -1) return "finish";
        int j = length-1;
        for(; j&gt;=0 &amp;&amp; array[j] &lt;= array[i]; j--);
        //swap i,j
        char tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
        //swap i,j
        for(int a=i+1, b=length-1; a<b;a++,b--){ tmp="array[a];" array[a]="array[b];" array[b]="tmp;" } return new string(array); 
        ``` 1.递增进位法 参考https: blog.csdn.net babynumber article details 43021021 定义一种数据结构，记录每个字符的逆序数（逆序数要求严格大于，不允许等于，则可在算法执行过程中去掉重复的排列）。举例，对于"bac"，a的逆序数为1，b的逆序数为0，c的逆序数为0。有重复字符的也类似，对于"baba"，a1的逆序数为1，a2的逆序数为2，b1的逆序数为0，b2的逆序数为0。 而且这种数据结构与字符的排列是一一对应的，即可由特定的一种排列求出每个字符的逆序数，也可由每个字符的逆序数还原出特定的一种排列。以"baba"为例，它的逆序数为 1200，我们先申请出足够的内存，“0000”表示申请一个空的四维数组，那么a1左边要留出一个空位，因为它的逆序数为1，得到"0a00"；a2的逆序数为2，所以要留出两个空位，得到"0a0a";b1的逆序数为0，不需要预留空位，得到"ba0a"; b2的逆序数为0，得到"baba"。 下面来演示如何由当前逆序数推出下一个排列（非字典序，一会解释）的逆序数： 首先我们找到逆序数的全集，仍以"baba"为例，a的逆序数最大为2，最小为0，b的逆序数最大为0，最小为0.则逆序数的全集为{0000，0100，0200，1000，1100，1200，2000，2100，2200} 如果把最低位的进制看作0，次低位的进制看作0，次高位的进制看作2，最高位的进制看作2，那么这9个数字其实是相邻的。所以只需实现这种特殊进制的加法运算就能求出下一个排列的逆序数，从而反推出当前的排列。由此可见，这跟字典序毫无关系，只能最后再统一排序了。 当然也可实现特殊进制的减法运算，也就是递减进位法。 时间复杂度o(n*n!) import java.util.*; public class solution { hashmap<character, integer> system = new HashMap<character, integer>();
    HashMap<integer, character> chaAt = new HashMap<integer, character>();
    int [] q;
    int length;
    public ArrayList<string> Permutation(String str) {
        ArrayList<string> r = new ArrayList<string>();
        HashSet<string> res = new HashSet<string>();
        if(str.length() == 0) return r;
        if(str.length() == 1) {
            r.add(str);
            return r;
        }
        init(str);
        res.add(output());
        boolean tag = false;
        while(true){
            tag = increase();
            System.out.println(tag);
            for(int i=0; i<length; i++) { system.out.print(q[i]); } system.out.println(); if(tag){ string s="output();" system.out.println(s); res.add(s); else break; r="new" arraylist<string>(res);
        Collections.sort(r);
        return r;
    }
    
    public void init(String str){
        //init length
        length = str.length();
        //
        char [] array = str.toCharArray();
        Arrays.sort(array);
        //init chaAt
        for(int i=0; i<length; i++){ chaat.put(i, array[i]); } init system for(int i="length-1;" i<length-1; if(array[i] < array[i+1]){ system.put(array[i], length-1-i); system.put(array[length-1], 0); q="new" int[length]; public boolean increase(){ int q[i]++; while(i>0 &amp;&amp; q[i] &gt; system.get(chaAt.get(i))){
            i--;
            q[i]++;
            q[i+1]=0;
        }
        if(q[i] &gt; system.get(chaAt.get(i))){
            return false;//overflow
        }
        return true;
    }
    
    public String output(){
        char [] array = new char[length];
        int [] mask = new int[length];
        for(int i=0; i<length; i++){ char tmp="chaAt.get(i);" int count="-1;" j="0;" for(j="0;" j<length; j++){ if(mask[j]="=" 0) count++; if(count="=" q[i]){ mask[j]="1;" array[j]="tmp;" break; } return new string(array); ``` 2.邻位互换法 参考https: blog.csdn.net babynumber article details 43866675 定义数据结构，为每个字符增加方向属性，向左或向右。如果当前字符指向的字符比他小，那么称它是可移动的，其余情况皆不可移动。 1、将给定序列初始化为字典序最小。每个字符的方向初始化为向左 2、找出最大的可移动字符c，并移动它 3、对于比c大的字符，将它们的方向调转 重复2、3直到所有字符均不可移动。 时间复杂度o(n*n!) 无字典序，但可去重。 import java.util.*; public class solution { [] dir; length; array; arraylist<string> Permutation(String str) {
        ArrayList<string> res = new ArrayList<string>();
        if(str.length() == 0) return res;
        init(str);
        res.add(new String(array));
        while(move()){
            res.add(new String(array));
        }
        Collections.sort(res);
        return res;
    }
    
    public void init(String str){
        length = str.length();
        dir = new int[length];
        array = str.toCharArray();
        Arrays.sort(array);
    }
    
    public boolean move(){
        int tag = -1;
        for(int i=0; i<length; i++){ int next="=" if(dir[i]="=" 0) next--; else next++; if(next="=" length || -1) continue; if(array[i]> array[next]){
                if(tag == -1 || array[i] &gt; array[tag]){
                    tag = i;
                }
            }
        }
        if(tag != -1){
            int next = tag;
            if(dir[tag] == 0) next--;
            else next++;
            char tmp = array[tag];
            array[tag] = array[next];
            array[next] = tmp;
            int tmpp = dir[next];
            dir[next] = dir[tag];
            dir[tag] = tmpp;
            for(int i=0; i<length; i++){ if(array[i]> array[next]) dir[i] = (dir[i]+1) % 2;
            }
            return true;
        }
        return false;
    }
}

3.递归回溯法 参考https://blog.csdn.net/BabyNumber/article/details/43924291 回溯法其实是在构造一棵生成树。对于"abc"，第一个位置有三种取值，第二个位置有两种取值，第三个位置有一种取值。定义函数next(k)，表示向第k个位置写值。递归的关键是维护一个剩余字符集合。 没能解决重复和有序问题。

import java.util.*;
public class Solution {
    ArrayList<string> res = new ArrayList<string>();
    HashSet<string> set = new HashSet<string>();
    int length;
    HashMap<character, integer> sta = new HashMap<character, integer>();
    char [] array;
    public ArrayList<string> Permutation(String str) {
    	set = new HashSet<string>();
    	res = new ArrayList<string>();
        if(str.length() == 0) return new ArrayList<string>();
        init(str);
        int k = 0;
        ArrayList<character> touse = new ArrayList<character>();
        for(char c : array) {
        	touse.add(c);
        }
        next(k, touse);
        res = new ArrayList<string>(set);
        Collections.sort(res);
        return res;
    }
 
    public void init(String str) {
        length = str.length();
        array = str.toCharArray();
        Arrays.sort(array);
        for (char c : array) {
            if (sta.containsKey(c))
                sta.put(c, sta.get(c) + 1);
            else
                sta.put(c, 1);
        }
    }
 
    public void next(int k, ArrayList<character> touse) {
 
        if (k == length) {
            String s = new String(array);
            if(!set.contains(s)) set.add(new String(array));
        }
        else {
            for (int i=0; i<touse.size(); i++) { char c="touse.get(i);" arraylist<character> to_use = new ArrayList<character>(touse);
            	to_use.remove(i);
                array[k] = c;
                next(k + 1, to_use);
            }
        }
    }
}

4.非递归回溯法 递归的很好理解，但是一般来说递归程序会有额外的开销，所以下面介绍非递归的回溯法。 所谓非递归就是手动模拟这棵树的生长过程。下面是使用深度优先遍历的方式构造树。不使用广度优先搜索的原因是，BFS需要保存非叶节点的信息，要占用额外的内存空间，对于该问题，使用DFS不需保存非叶节点，可以按照规定的顺序生成儿子节点以及回到父亲节点。 回溯法分为前进和后退两个过程，前进到叶子节点后要返回父节点。 forward()：用剩余的字符填满剩余的空位，填满就到了叶节点，然后执行back()。（这里为了保证生成的排列有序，我们规定优先使用小字符，所以用一个最小堆来保存剩余字符。但是并不能最大化最小堆返回最小值O(1)的效果，下面会解释，但我还是觉得大多数时候可以在O(1)时间内得到这个最小值，于是保留了最小堆的设计）（很遗憾，使用最小堆并没有什么效果，与使用线性表无差，实验我做过了）。 back()：当到达叶节点后，需要回溯到父节点，然后需要判断父节点是否有兄弟，如果有兄弟则停在兄弟节点处，重新执行forward()。但我们知道兄弟节点是没有相对位置关系的，为了不陷入死循环，我们必须规定兄弟节点之间的顺序，于是使用字典序。举例：a__的儿子有ab_和ac_，我们规定ab_是大儿子，即back()时只能从ab_回溯到ac_，不能反过来。 重复forward()和back()，当不能回溯时停止。 回溯法不能保证去重。

import java.util.*;
public class Solution {
    HashSet<string> res = new HashSet<string>();
    char[] array;
    PriorityQueue<character> pq;
    int length;
 
    public ArrayList<string> Permutation(String str) {
        if (str.length() == 0)
            return new ArrayList<string>();
        init(str);
        boolean tag = true;
        while (tag) {
            forward();
            String s = new String(array);
            if (!res.contains(s))
                res.add(s);
            tag = back();
        }
        ArrayList<string> r = new ArrayList<string>(res);
        Collections.sort(r);
        return r;
    }
 
    public void init(String str) {
        length = str.length();
        pq = new PriorityQueue<character>(length);
        array = str.toCharArray();
        for (char c : array) {
            pq.offer(c);
        }
        res = new HashSet<string>();
    }
 
    public void forward() {
        int k = length - pq.size();
        for (; k &lt; length; k++) {
            array[k] = pq.poll();
        }
    }
 
    public boolean back() {
        int k = length - pq.size() - 1;
        Stack<character> s = new Stack<character>();
        while (k != -1) {
            while (!pq.isEmpty()) {
                char tmp = pq.poll();
                if (tmp &lt;= array[k])
                    s.push(tmp);
                else {
                    pq.offer(tmp);
                    break;
                }
            }
            if (!pq.isEmpty()) {
                s.push(array[k]);
                array[k] = pq.poll();
                while (!s.isEmpty()) {
                    pq.offer(s.pop());
                }
                return true;
            }
            while (!s.isEmpty()) {
                pq.offer(s.pop());
            }
            pq.offer(array[k]);
            k--;
        }
        return false;
    }
}

5.递归法 参考@HAHA7877在讨论区的发言，图文并茂，写的很好。我更改了去重的部分，提高了运行的时间效率。 同样是利用了回溯法的思想，但它生成树的思路不是填空，而是交换当前位置字符与其他位置。 不能解决重复和字典序问题。

import java.util.*;
public class Solution {
	HashSet<string> res = new HashSet<string>();
    ArrayList<string> r = new ArrayList<string>();
    int length;
    char [] array;
    public ArrayList<string> Permutation(String str) {
        if(str.length() == 0) return new ArrayList<string>();
        init(str);
        perm(0);
        r = new ArrayList<string>(res);
        Collections.sort(r);
        return r;
    }
 
    public void init(String str){
        length = str.length();
        array = str.toCharArray();
        Arrays.sort(array);
        res = new HashSet<string>();
    }
 
    public void perm(int k){
        if(k == length){
            String s = new String(array);
            if(!res.contains(s)) res.add(s);
        }
        else{
            int j=k;
            for(; j</string></string></string></string></string></string></string></string></character></character></string></character></string></string></string></string></character></string></string></character></touse.size();></character></string></character></character></string></string></string></string></character,></character,></string></string></string></string></length;></length;></string></string></length;></length;></length;></string></string></string></string></string></integer,></integer,></character,></b;a++,b--){></string></string></string>