首页 > 试题广场 > 字符串的排列
[编程题]字符串的排列
  • 热度指数:761675 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

示例1

输入

"ab"

输出

["ab","ba"]
推荐
 /**
     * 1、递归算法
     *
     * 解析:http://www.cnblogs.com/cxjchen/p/3932949.html  (感谢该文作者!)
     *
     * 对于无重复值的情况
     *
     * 固定第一个字符,递归取得首位后面的各种字符串组合;
     * 再把第一个字符与后面每一个字符交换,并同样递归获得首位后面的字符串组合; *递归的出口,就是只剩一个字符的时候,递归的循环过程,就是从每个子串的第二个字符开始依次与第一个字符交换,然后继续处理子串。
     *
     * 假如有重复值呢?
     * *由于全排列就是从第一个数字起,每个数分别与它后面的数字交换,我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。
     * 例如abb,第一个数与后面两个数交换得bab,bba。然后abb中第二个数和第三个数相同,就不用交换了。
     * 但是对bab,第二个数和第三个数不 同,则需要交换,得到bba。
     * 由于这里的bba和开始第一个数与第三个数交换的结果相同了,因此这个方法不行。
     *
     * 换种思维,对abb,第一个数a与第二个数b交换得到bab,然后考虑第一个数与第三个数交换,此时由于第三个数等于第二个数,
     * 所以第一个数就不再用与第三个数交换了。再考虑bab,它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕!
     *
     *
     * @param str
     * @return
     */

public ArrayList<String> Permutation(String str){

        ArrayList<String> list = new ArrayList<String>();
        if(str!=null && str.length()>0){
            PermutationHelper(str.toCharArray(),0,list);
            Collections.sort(list);
        }
        return list;
    }
    private void PermutationHelper(char[] chars,int i,ArrayList<String> list){
        if(i == chars.length-1){
            list.add(String.valueOf(chars));
        }else{
            Set<Character> charSet = new HashSet<Character>();
            for(int j=i;j<chars.length;++j){
                if(j==i || !charSet.contains(chars[j])){
                    charSet.add(chars[j]);
                    swap(chars,i,j);
                    PermutationHelper(chars,i+1,list);
                    swap(chars,j,i);
                }
            }
        }
    }

    private void swap(char[] cs,int i,int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }

/**
     * 2、字典序排列算法
     *
     * 可参考解析: http://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html  (感谢作者)
     *
     * 一个全排列可看做一个字符串,字符串可有前缀、后缀。
     * 生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。
     * 这就要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。
     *
     * [例]839647521是1--9的排列。1—9的排列最前面的是123456789,最后面的987654321,
     * 从右向左扫描若都是增的,就到了987654321,也就没有下一个了。否则找出第一次出现下降的位置。
     *
     * 【例】 如何得到346987521的下一个
     * 1,从尾部往前找第一个P(i-1) < P(i)的位置
     * 3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
     * 最终找到6是第一个变小的数字,记录下6的位置i-1
     *
     * 2,从i位置往后找到最后一个大于6的数
     * 3 4 6 -> 9 -> 8 -> 7 5 2 1
     * 最终找到7的位置,记录位置为m
     *
     * 3,交换位置i-1和m的值
     * 3 4 7 9 8 6 5 2 1
     * 4,倒序i位置后的所有数据
     * 3 4 7 1 2 5 6 8 9
     * 则347125689为346987521的下一个排列
     *
     * @param str
     * @return
     */

public ArrayList<String> Permutation2(String str){
        ArrayList<String> list = new ArrayList<String>();
        if(str==null || str.length()==0){
            return list;
        }
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        list.add(String.valueOf(chars));
        int len = chars.length;
        while(true){
            int lIndex = len-1;
            int rIndex;
            while(lIndex>=1 && chars[lIndex-1]>=chars[lIndex]){
                lIndex--;
            }
            if(lIndex == 0)
                break;
            rIndex = lIndex;
            while(rIndex<len && chars[rIndex]>chars[lIndex-1]){
                rIndex++;
            }
            swap(chars,lIndex-1,rIndex-1);
            reverse(chars,lIndex);

            list.add(String.valueOf(chars));
        }

        return list;
    }

    private void reverse(char[] chars,int k){
        if(chars==null || chars.length<=k)
            return;
        int len = chars.length;
        for(int i=0;i<(len-k)/2;i++){
            int m = k+i;
            int n = len-1-i;
            if(m<=n){
                swap(chars,m,n);
            }
        }

    }

编辑于 2018-12-26 14:11:30 回复(37)

基于回溯法思想:

图片说明

Java代码:

import java.util.List;
import java.util.Collections;
import java.util.ArrayList;

public class Solution {
    public static void main(String[] args) {
        Solution p = new Solution();
        System.out.println(p.Permutation("abc").toString());
    }

    public ArrayList<String> Permutation(String str) {
        List<String> res = new ArrayList<>();
        if (str != null && str.length() > 0) {
            PermutationHelper(str.toCharArray(), 0, res);
            Collections.sort(res);
        }
        return (ArrayList)res;
    }

    public void PermutationHelper(char[] cs, int i, List<String> list) {
        if (i == cs.length - 1) {
            String val = String.valueOf(cs);
            if (!list.contains(val)) 
                list.add(val);
        } else {
            for (int j = i; j < cs.length; j++) {
                swap(cs, i, j);
                PermutationHelper(cs, i+1, list);
                swap(cs, i, j);
            }
        }
    }

    public void swap(char[] cs, int i, int j) {
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}
编辑于 2018-03-20 19:17:11 回复(53)
把高分答案理解了一下,图也盗一下


import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        List<String> resultList = new ArrayList<>();
        if(str.length() == 0)
            return (ArrayList)resultList;
        //递归的初始值为(str数组,空的list,初始下标0)
        fun(str.toCharArray(),resultList,0);
        Collections.sort(resultList);
        return (ArrayList)resultList;
    }
    
    private void fun(char[] ch,List<String> list,int i){
        //这是递归的终止条件,就是i下标已经移到char数组的末尾的时候,考虑添加这一组字符串进入结果集中
        if(i == ch.length-1){
            //判断一下是否重复
            if(!list.contains(new String(ch))){
                list.add(new String(ch));
                return;
            }
        }else{
            //这一段就是回溯法,这里以"abc"为例
            
            //递归的思想与栈的入栈和出栈是一样的,某一个状态遇到return结束了之后,会回到被调用的地方继续执行
            
            //1.第一次进到这里是ch=['a','b','c'],list=[],i=0,我称为 状态A ,即初始状态
            //那么j=0,swap(ch,0,0),就是['a','b','c'],进入递归,自己调自己,只是i为1,交换(0,0)位置之后的状态我称为 状态B 
            //i不等于2,来到这里,j=1,执行第一个swap(ch,1,1),这个状态我称为 状态C1 ,再进入fun函数,此时标记为T1,i为2,那么这时就进入上一个if,将"abc"放进list中
            /////////////-------》此时结果集为["abc"]
            
            //2.执行完list.add之后,遇到return,回退到T1处,接下来执行第二个swap(ch,1,1),状态C1又恢复为状态B
            //恢复完之后,继续执行for循环,此时j=2,那么swap(ch,1,2),得到"acb",这个状态我称为C2,然后执行fun,此时标记为T2,发现i+1=2,所以也被添加进结果集,此时return回退到T2处往下执行
            /////////////-------》此时结果集为["abc","acb"]
            //然后执行第二个swap(ch,1,2),状态C2回归状态B,然后状态B的for循环退出回到状态A
            
            //             a|b|c(状态A)
            //               |
            //               |swap(0,0)
            //               |
            //             a|b|c(状态B)
            //             /  \
            //   swap(1,1)/    \swap(1,2)  (状态C1和状态C2)
            //           /      \
            //         a|b|c   a|c|b
            
            //3.回到状态A之后,继续for循环,j=1,即swap(ch,0,1),即"bac",这个状态可以再次叫做状态A,下面的步骤同上
            /////////////-------》此时结果集为["abc","acb","bac","bca"]
            
            //             a|b|c(状态A)
            //               |
            //               |swap(0,1)
            //               |
            //             b|a|c(状态B)
            //             /  \
            //   swap(1,1)/    \swap(1,2)  (状态C1和状态C2)
            //           /      \
            //         b|a|c   b|c|a
            
            //4.再继续for循环,j=2,即swap(ch,0,2),即"cab",这个状态可以再次叫做状态A,下面的步骤同上
            /////////////-------》此时结果集为["abc","acb","bac","bca","cab","cba"]
            
            //             a|b|c(状态A)
            //               |
            //               |swap(0,2)
            //               |
            //             c|b|a(状态B)
            //             /  \
            //   swap(1,1)/    \swap(1,2)  (状态C1和状态C2)
            //           /      \
            //         c|b|a   c|a|b
            
            //5.最后退出for循环,结束。
            
            for(int j=i;j<ch.length;j++){
                swap(ch,i,j);
                fun(ch,list,i+1);
                swap(ch,i,j);
            }
        }
    }
    
    //交换数组的两个下标的元素
    private void swap(char[] str, int i, int j) {
            if (i != j) {
                char t = str[i];
                str[i] = str[j];
                str[j] = t;
            }
        }
    } 

发表于 2018-04-26 16:34:54 回复(38)
思路:递归法,问题转换为先固定第一个字符,求剩余字符的排列;求剩余字符排列时跟原问题一样。
(1) 遍历出所有可能出现在第一个位置的字符(即:依次将第一个字符同后面所有字符交换);
(2) 固定第一个字符,求后面字符的排列(即:在第1步的遍历过程中,插入递归进行实现)。
需要注意的几点:
(1) 先确定递归结束的条件,例如本题中可设begin == str.size() - 1; 
(2) 形如 aba 或 aa 等特殊测试用例的情况,vector在进行push_back时是不考虑重复情况的,需要自行控制;
(3) 输出的排列可能不是按字典顺序排列的,可能导致无法完全通过测试用例,考虑输出前排序,或者递归之后取消复位操作。
参考代码如下:
class Solution {
public:
    vector<string> Permutation(string str) 
    {
        vector<string> result;
        if(str.empty()) return result;
        
        Permutation(str,result,0);
        
        // 此时得到的result中排列并不是字典顺序,可以单独再排下序
        sort(result.begin(),result.end());
        
        return result;
    }
    
    void Permutation(string str,vector<string> &result,int begin)
    {
        if(begin == str.size()-1) // 递归结束条件:索引已经指向str最后一个元素时
        {
            if(find(result.begin(),result.end(),str) == result.end())
            {
                // 如果result中不存在str,才添加;避免aa和aa重复添加的情况
                result.push_back(str);
            }
        }
        else
        {
            // 第一次循环i与begin相等,相当于第一个位置自身交换,关键在于之后的循环,
            // 之后i != begin,则会交换两个不同位置上的字符,直到begin==str.size()-1,进行输出;
            for(int i=begin;i<str.size();++i)
            {
                swap(str[i],str[begin]);
                Permutation(str,result,begin+1);
                swap(str[i],str[begin]); // 复位,用以恢复之前字符串顺序,达到第一位依次跟其他位交换的目的
            }
        }
    }
    
    void swap(char &fir,char &sec)
    {
        char temp = fir;
        fir = sec;
        sec = temp;
    }
};

发表于 2016-08-23 11:17:45 回复(29)
# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        if len(ss) <= 1:
            return ss
        res = set()
        # 遍历字符串,固定第一个元素,第一个元素可以取a,b,c...,然后递归求解
        for i in range(len(ss)):
            for j in self.Permutation(ss[:i] + ss[i+1:]): # 依次固定了元素,其他的全排列(递归求解)
                res.add(ss[i] + j) # 集合添加元素的方法add(),集合添加去重(若存在重复字符,排列后会存在相同,如baa,baa)
        return sorted(res)         # sorted()能对可迭代对象进行排序,结果返回一个新的list


编辑于 2019-08-26 21:05:38 回复(18)
迭代算法:字典生成算法
public ArrayList<String> Permutation(String str) {
       ArrayList<String> res = new ArrayList<>();

        if (str != null && str.length() > 0) {
            char[] seq = str.toCharArray();
            Arrays.sort(seq); //排列
            res.add(String.valueOf(seq)); //先输出一个解

            int len = seq.length;
            while (true) {
                int p = len - 1, q;
                //从后向前找一个seq[p - 1] < seq[p]
                while (p >= 1 && seq[p - 1] >= seq[p]) --p;
                if (p == 0) break; //已经是“最小”的排列,退出
                //从p向后找最后一个比seq[p]大的数
                q = p; --p;
                while (q < len && seq[q] > seq[p]) q++;
                --q;
                //交换这两个位置上的值
                swap(seq, q, p);
                //将p之后的序列倒序排列
                reverse(seq, p + 1);
                res.add(String.valueOf(seq));
            }
        }

        return res;
    }
    
    public static void reverse(char[] seq, int start) {
        int len;
        if(seq == null || (len = seq.length) <= start)
            return;
        for (int i = 0; i < ((len - start) >> 1); i++) {
            int p = start + i, q = len - 1 - i;
            if (p != q)
                swap(seq, p, q);
        }
    }
    
    public static void swap(char[] cs, int i, int j) {
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
递归算法:
public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();

        if (str != null && str.length() > 0) {
            PermutationHelper(str.toCharArray(), 0, res);
            Collections.sort(res);
        }

        return res;
    }

    private static void PermutationHelper(char[] cs, int i, ArrayList<String> list) {
        if(i == cs.length - 1) { //解空间的一个叶节点
            list.add(String.valueOf(cs)); //找到一个解
        } else {
            for(int j = i; j < cs.length; ++j) {
                if(j == i || cs[j] != cs[i]) {
                    SwapUtil.swap(cs, i, j);
                    PermutationHelper(cs, i + 1, list);
                    SwapUtil.swap(cs, i, j); //复位
                }
            }
        }
    }

发表于 2015-12-21 15:18:15 回复(14)
记得全排列这种写法还是在学校图书馆看到的,回溯法中,当初理解了好久。
import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       	ArrayList<String> re = new ArrayList<String>();
		if (str == null || str.length() == 0) {
			return re;
		}
		HashSet<String> set = new HashSet<String>();
		fun(set, str.toCharArray(), 0);
		re.addAll(set);
		Collections.sort(re);
		return re;
	}
    void fun(HashSet<String> re, char[] str, int k) {
		if (k == str.length) {
			re.add(new String(str));
			return;
		}
		for (int i = k; i < str.length; i++) {
			swap(str, i, k);
			fun(re, str, k + 1);
			swap(str, i, k);
		}
	}
    void swap(char[] str, int i, int j) {
		if (i != j) {
			char t = str[i];
			str[i] = str[j];
			str[j] = t;
		}
	}
}

发表于 2015-10-09 23:01:25 回复(36)
class Solution {
public:
    vector<string> Permutation(string str) {
        if(str.empty())
            return ans;
        chang(str, 0, str.size()); 
        sort(ans.begin(),ans.end());
        auto it = unique(ans.begin(),ans.end());
        ans.erase(it,ans.end());
        return ans;
        
    }
    void chang(string &str,int start,int len){
        if(start == len)
            ans.push_back(str);
        //
        for(int i = start; i < len; i++){
            swap(str[start],str[i]);
            chang(str, start+1,len);
            swap(str[start],str[i]);
        }  
    }
        
    vector<string> ans;
};

发表于 2016-07-13 12:03:53 回复(6)
class Solution {
public:
    vector<string> Permutation(string str) {
        //可以用递归来做
        vector<string> array;
        if(str.size()==0)
            return array;
        Permutation(array, str, 0);
        sort(array.begin(), array.end());
        return array;
    }
    
    void Permutation(vector<string> &array, string str, int begin)//遍历第begin位的所有可能性
    {
    	if(begin==str.size()-1)
            array.push_back(str);
        for(int i=begin; i<=str.size()-1;i++)
        {
        	if(i!=begin && str[i]==str[begin])//有重复字符时,跳过
                continue;
            swap(str[i], str[begin]);//当i==begin时,也要遍历其后面的所有字符;
            						//当i!=begin时,先交换,使第begin位取到不同的可能字符,再遍历后面的字符
            Permutation(array, str, begin+1);//遍历其后面的所有字符;
            
            swap(str[i], str[begin]);//为了防止重复的情况,还需要将begin处的元素重新换回来
            
            /*举例来说“abca”,为什么使用了两次swap函数
            	交换时是a与b交换,遍历;
            	交换时是a与c交换,遍历;(使用一次swap时,是b与c交换)
                交换时是a与a不交换;
                */
        }
    }
};

发表于 2015-09-04 23:40:55 回复(32)

JS的两种做法来啦来啦,觉得可以给个赞

递归全排列法:

就是剑指offer上的做法,也比较容易理解,不过挺少人答的也就是
  1. 把字符串分为两部分:第一部分为第一个字符,第二部分为第一个字符以后的字符串。
  2. 然后接下来求后面那部分的全排列。
  3. 再将第一个字符与后面的那部分字符逐个交换
代码如下
function Permutation(str)
{
    let res=[];
    if(str.length<=0) return res;
    arr=str.split("");//将字符串转化为字符数组
    res=permutate(arr,0,res);
    res=[...new Set(res)];
    res.sort();
    return res;
}
function permutate(arr,index,res){
    if(arr.length==index){
        let s="";
        for(let i=0;i<arr.length;i++){
            s+=arr[i];
        }
        return res.push(s);
    }else{
        for(var i=index;i<arr.length;i++){
            [arr[index],arr[i]]=[arr[i],arr[index]];
            permutate(arr,index+1,res);
            [arr[index],arr[i]]=[arr[i],arr[index]];
        }
    }
    return res;
}

回溯法

也就是利用树去尝试不同的可能性,不断地去字符串数组里面拿一个字符出来拼接字符串,当字符串数组被拿空时,就把结果添加进结果数组里,然后回溯上一层。(通过往数组加回去字符以及拼接的字符串减少一个来回溯。
代码如下
function Permutation(str)
{
    let res=[],pStr="";
    if(str.length<=0) return res;
    arr=str.split("");//将字符串转化为字符数组
    res=permutate(arr,pStr,res);
    return res;
}
function permutate(arr,pStr,res){
    if(arr.length==0){
        return res.push(pStr);
    }else{
        let isRepeated=new Set();
        for(let i=0;i<arr.length;i++){
            if(!isRepeated.has(arr[i])){//避免相同的字符交换
                let char=arr.splice(i,1)[0];
                pStr+=char;
                permutate(arr,pStr,res);
                arr.splice(i,0,char);//恢复字符串,回溯
                pStr=pStr.slice(0,pStr.length-1);//回溯
                isRepeated.add(char);
            }
        }
    }
    return res;
}

发表于 2018-04-06 06:50:20 回复(4)
用DFS做得,顺便练习下,嘿嘿

import java.util.*;

public class Solution {
    private char [] seqs;
    private Integer [] book;
    //用于结果去重
    private HashSet<String> result = new HashSet<String>();
    /**
     * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
     * 例如输入字符串abc,则打印出由字符a,b,c
     * 所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。
       输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。\
     * @param str
     * @return
     */
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> arrange = new ArrayList<String>();
        if(str == null || str.isEmpty()) return arrange;
        char[] strs = str.toCharArray();
        seqs = new char[strs.length];
        book = new Integer[strs.length];
        for (int i = 0; i < book.length; i++) {
            book[i] = 0;
        }
        dfs(strs, 0);
        arrange.addAll(result);
        Collections.sort(arrange);
        return arrange;
    }

    /**
     * 深度遍历法
     */
    private void dfs(char[] arrs, int step){
        //走完所有可能 记录排列
        if(arrs.length == step){
            String str = "";
            for (int i = 0; i < seqs.length; i++) {
                str += seqs[i];
            }
            result.add(str);
            return; //返回上一步
        }
        //遍历整个序列,尝试每一种可能
        for (int i = 0; i < arrs.length; i++) {
            //是否走过
            if(book[i] == 0){
                seqs[step] = arrs[i];
                book[i] = 1;
                //下一步
                dfs(arrs, step + 1);
                //走完最后一步 后退一步
                book[i] = 0;
            }
        }
    }
}

发表于 2015-09-11 10:14:11 回复(12)
//比较简单的代码,这个题目算经典的
class Solution {
public:
    vector<string> Permutation(string str) {        
        if(str!="") dfs(str, 0);
        return ret;
    }
private:
    vector<string> ret;
    void dfs(string str, int s){
        int sz = str.size();
        if(s==sz){
            ret.push_back(str);
            return;
        }
        for(int i = s; i < sz; ++i){
            if(i!=s && str[s]==str[i]) continue;
            swap(str[s], str[i]);
            dfs(str, s+1);
        }
    }   
};

发表于 2017-05-16 16:05:18 回复(10)
class Solution:
    def Permutation(self, ss):
        # write code here
        res = []
        if len(ss) < 2:
            return ss.split()
        for i in range(len(ss)):
            for n in map(lambda x: x+ ss[i], self.Permutation(ss[:i]+ss[i+1:])):
                if n not in res:
                    res.append(n)
        return sorted(res)

发表于 2017-11-02 21:25:49 回复(3)
利用栈来实现排序,真的是太巧妙了,分享给大家。

public class Solution {
    public ArrayList<String> Permutation(String str) {
        TreeSet<String> tree = new TreeSet<>();
       Stack<String[]> stack = new Stack<>();
			ArrayList<String> results = new ArrayList<>();
			stack.push(new String[]{str,""});
			do{
				String[] popStrs = stack.pop();
				String oldStr = popStrs[1];
				String statckStr = popStrs[0];
				for(int i =statckStr.length()-1;i>=0;i--){
					String[] strs = new String[]{statckStr.substring(0,i)+statckStr.substring(i+1),oldStr+statckStr.substring(i,i+1)};
					if(strs[0].length()==0){
						tree.add(strs[1]);
					}else{
						stack.push(strs);
					}
				}
			}while(!stack.isEmpty());
        for(String s : tree)
            results.add(s);
        return results;
    }
}


发表于 2015-10-17 10:59:34 回复(12)

python solution:

# -*- coding:utf-8 -*-
import itertools
class Solution:
    def Permutation(self, ss):
        # write code here
        result=[]
        if not ss:
            return []
        else:
            res=itertools.permutations(ss)
            for i in res:
                if "".join(i) not in result:
                    result.append("".join(i))
        return result
发表于 2017-10-14 13:56:57 回复(24)
# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        if not ss:
            return []
        if len(ss) == 1:
            return [ss]
        ret = []
        #遍历字符串,固定第一个元素,然后递归求解
        for i in range(len(ss)):
            for j in self.Permutation(ss[:i]+ss[i+1:]):
                ret.append(ss[i]+j)
        #通过set进行去重,sorted进行重新排序
        return sorted(list(set(ret))) 
发表于 2018-04-08 09:52:05 回复(2)
/*
*字典排序算法
*一个全排列可看做一个字符串,字符串可有前缀、后缀。
*生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。
*[例]839647521是1--9的排列。1—9的排列最前面的是123456789,最后面的987654321,从右向左扫描若都是增的,就到了987654321,也就没有下一个了。否则找出第一次出现下降的位置。
* 【例】 一般而言,设P是[1,n]的一个全排列。
*      P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn
*    find:  j=max{i|Pi<Pi+1}
*         k=max{i|Pi>Pj}
*      1,  对换Pj,Pk,
*      2,  将Pj+1…Pk-1PjPk+1…Pn翻转
*          P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个  
*【例】 如何得到346987521的下一个
*    1,从尾部往前找第一个P(i-1) < P(i)的位置
*            3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
*        最终找到6是第一个变小的数字,记录下6的位置i-1
*    2,从i位置往后找到最后一个大于6的数
*            3 4 6 -> 9 -> 8 -> 7 5 2 1
*        最终找到7的位置,记录位置为m
*    3,交换位置i-1和m的值
*            3 4 7 9 8 6 5 2 1
*    4,倒序i位置后的所有数据
*            3 4 7 1 2 5 6 8 9
*    则347125689为346987521的下一个排列
*/

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<String>();
        
       if(str == null || str.length()==0) {
           return list;
       }
       char[] chars = str.toCharArray();
       Arrays.sort(chars);
        list.add(String.valueOf(chars));
        int len = chars.length;
        while(true) {
            int lIndex = len-1;
//从右往左,找到每一个开始变小数字的位置
            while(lIndex>0 && chars[lIndex-1]>=chars[lIndex]) {
                lIndex--;
            }
//从右向左扫描若都是增的,代表全排列结束
            if(lIndex == 0) {
                break;
            }
            int rIndex = lIndex;
//从开始变小数字后面开始向右遍历,找到最后一个比这个数字大的数
            while(rIndex<len && chars[rIndex]>chars[lIndex-1]) {
                rIndex++;
            }
//交换lIndex-1和rIndex-1这两个数的位置
            swap(chars,lIndex-1,rIndex-1);
//lIndex开始逆序
            reverse(chars,lIndex);
            
            list.add(String.valueOf(chars));
        }
        
        return list;
    }
    
    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
    
    private void reverse(char[] chars,int k) {
        if(chars==null || chars.length<=k) {
            return;
        }
        int len = chars.length;
        for(int i=0; i<(len-k)/2; i++) {
            int m = k+i;
            int n = len-1-i;
            swap(chars,m,n);
        }
    } 
}


/*
*递归算法
*于无重复值的情况
*1、定第一个字符,递归取得首位后面的各种字符串组合;
*2、再把第一个字符与后面每一个字符交换,并同样递归获得首位后面的字符串组合; 
*递归的出口,就是只剩一个字符的时候。
*递归的循环过程,就是从每个子串的第二个字符开始依次与第一个字符交换,然后继续处理子串。
*假如有重复值呢?
*由于全排列就是从第一个数字起,每个数分别与它后面的数字交换,我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。     
*例如abb,第一个数与后面两个数交换得bab,bba。然后abb中第二个数和第三个数相同,就不用交换了。
*由于这里的bba和开始第一个数与第三个数交换的结果相同了,因此这个方法不行。     
*换种思维,对abb,第一个数a与第二个数b交换得到bab,然后考虑第一个数与第三个数交换,此时由于第三个数等于第二个数,
*所以第一个数就不再用与第三个数交换了。再考虑bab,它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕!
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Set;
import java.util.HashSet;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<String>();
        if(str != null && str.length()>0) {
            PermutationHelp(str.toCharArray(),0,list);
            Collections.sort(list);
        }
        
        return list;
    }
    
    public void PermutationHelp(char[] chars, int i, ArrayList<String> list) {
        if(i == chars.length-1) {
            list.add(String.valueOf(chars));
        } else {
            Set<Character> set = new HashSet<Character>();//去掉重复交换的字符
            for(int j=i; j<chars.length; j++) {
                if(j==i || !set.contains(chars[j])) {
                    set.add(chars[j]);
                    swap(chars,i,j);//交换第一个字符与其它每个字符的位置
                    PermutationHelp(chars,i+1,list);
                    swap(chars,i,j);//为了防止重复的情况,还需要将begin处的元素重新换回来
                }
            }
        }
    }
    
    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
    
    
}
发表于 2017-03-13 15:26:05 回复(0)
//简短的AC代码。调用了STL的next_permutation函数
 vector<string> Permutation(string str) {
        vector<string> answer;
        if(str.empty())
            return answer;        
        sort(str.begin(),str.end());
        do{
            answer.push_back(str);
        }
        while(next_permutation(str.begin(),str.end()));
        return answer;
}

编辑于 2015-07-11 09:28:50 回复(14)
class Solution {
public:
void solve(vector<string> &ans, string &str, int pos, int arr[], int n){
    if(pos == n){
        string tmp = "";
        int flag = 1;
        for(int i=0;i<pos;i++) tmp += str[arr[i]];
        for(int i=0;i<ans.size();i++) if(tmp == ans[i]) flag = 0;
        if(flag) ans.push_back(tmp);
    }
    else for(int i=0;i<str.length();i++){
        int ok = 1;
        for(int j=0;j<pos;j++)
            if(arr[j] == i) ok = 0;
        if(ok){
            arr[pos] = i;
            solve(ans, str, pos+1, arr, n);
        }
    }
}

    vector<string> Permutation(string str) {
        sort(str.begin(), str.end());
        vector<string> ans; int s[10];
        if(!str.empty()) solve(ans, str, 0, s, str.length());
        return ans;
    }
};
发表于 2018-12-06 16:01:00 回复(0)
//参照剑指offer的思路
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.empty())
            return res;
        string tmp="";
        recur(str,res,tmp,0);
        return res;
    }
    void recur(string str,vector<string> &res,string &tmp,int start){
        if(start==str.size()){
            res.push_back(tmp);
            return;
        }    
        for(int i=start;i<str.size();i++){
            //判断要交换的字符是否相同,相同就不用交换直接跳过(除了start位置与自己交换的情况)
            if(i!=start&&str[start]==str[i])
                continue;
            swap(str[start],str[i]);
            tmp+=str[start];
            recur(str,res,tmp,start+1);  
            tmp.pop_back();   
        }
    }  
};

发表于 2017-05-15 21:56:30 回复(5)
public ArrayList<String> Permutation(String str) {
		ArrayList<String> result = new ArrayList<String>();
		if (str == null || str.length() > 9 || str.length()==0) {
			return result;
		}
		str = str.trim();
		Permutation(str.toCharArray(), 0, result);
//		HashSet<String> hs = new HashSet<String>(result);  //此仅去重,没有字典序排列,可能错误
//		new ArrayList<String>(hs);
		Collections.sort(result);  //字典序排列  有些oj要求
		return result;

	}

	public static void Permutation(char[] data, int beginIdx,ArrayList<String> result) {
		if (beginIdx == data.length) {
			result.add(new String(data));
		} else {
			for (int i = beginIdx; i < data.length; ++i) {
				//有重复字符时,跳过
				if(i!=beginIdx && data[i]==data[beginIdx]) continue; 
				//当i==begin时,也要遍历其后面的所有字符;
                //当i!=begin时,先交换,使第begin位取到不同的可能字符,再遍历后面的字符
				char temp = data[beginIdx];
				data[beginIdx] = data[i];
				data[i] = temp;
				
				Permutation(data, beginIdx + 1, result);
				
				//为了防止重复的情况,还需要将begin处的元素重新换回来           恢复打扫战场,恢复为原来子串, data共享
				temp = data[beginIdx];
				data[beginIdx] = data[i];
				data[i] = temp;
				
				/* 举例来说“b(acd)” acd排列 ,为什么使用了两次swap函数?    函数栈变化恢复 ,  "acd第一次输出 cda后,完全退栈 返回data应该还是acd"
				                             交换栈                       退栈
				        bacd       bacd
				        bcad       bcad
				        bcda 打印  -> bcda
                */
			}
		}
	}

编辑于 2015-11-18 16:51:40 回复(5)