/*
     * eg: abc =>{a,bc},{b,ac},{c,ab}
     * =>{ca,b},{cb,a}
     * =>cba,cab
     * =>{ba,c},{bc,a}
     * =>bca,bac
     * =>{ab,c},{ac,b}
     * =>acb,abc
     */
    public void nonRecpermute(String prefix, String word)
    {
        String[] currentstr ={prefix,word};
        Stack<String[]> stack = new Stack<String[]>();
        stack.add(currentstr);
        while(!stack.isEmpty())
        {
            currentstr = stack.pop();
            String currentPrefix = currentstr[0];
            String currentWord = currentstr[1];
            if(currentWord.equals(""))
            {
                System.out.println("Word ="+currentPrefix);
            }
            for(int i=0;i<currentWord.length();i++)
            {
                String[] newstr = new String[2];
                newstr[0]=currentPrefix + String.valueOf(currentWord.charAt(i));
                newstr[1] = currentWord.substring(0, i);
                if(i<currentWord.length()-1)
                {
                    newstr[1] = newstr[1]+currentWord.substring(i+1);
                }
                stack.push(newstr);
            }

        }

    }

简单的解决方案，利用swift语言的特点，数组是值类型。

func permutation(chrs: [String], arr: [String], result: inout [[String]]) {
   if arr.count == chrs.count {
       result.append(arr)
       return
   }

   for chr in chrs {
       var arr = arr
       if !arr.contains(chr) {
           arr.append(chr)
           permutation(chrs: chrs, arr: arr, result: &result)
       }
   }
}

func test() {
   var result = [[String]]()
   let chrs = ["a", "b", "c", "d"]
   permutation(chrs: chrs, arr: [], result: &result)
}

复杂度O(n * n!)

其中一个简单的解决方案是使用两个指针继续递归地交换字符。

public static void main(String[] args)
{
    String str="abcdefgh";
    perm(str);
}
public static void perm(String str)
{  char[] char_arr=str.toCharArray();
    helper(char_arr,0);
}
public static void helper(char[] char_arr, int i)
{
    if(i==char_arr.length-1)
    {
        // print the shuffled string 
            String str="";
            for(int j=0; j<char_arr.length; j++)
            {
                str=str+char_arr[j];
            }
            System.out.println(str);
    }
    else
    {
    for(int j=i; j<char_arr.length; j++)
    {
        char tmp = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp;
        helper(char_arr,i+1);
        char tmp1 = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp1;
    }
}
}

使用位操作可以很容易地做到这一点。“我们都知道，任何给定的有N个元素的集合有2N个可能的子集。如果我们用一个位来表示子集中的每个元素呢?位可以是0或1，因此我们可以用它来表示对应的元素是否属于这个给定的子集。所以每个位模式代表一个子集。”(复制文本)

private void getPermutation(String str)
        {
            if(str==null)
                return;
            Set<String> StrList = new HashSet<String>();
            StringBuilder strB= new StringBuilder();
            for(int i = 0;i < (1 << str.length()); ++i)
            {
                strB.setLength(0); //clear the StringBuilder
                for(int j = 0;j < str.length() ;++j){
                    if((i & (1 << j))>0){  // to check whether jth bit is set
                        strB.append(str.charAt(j));
                    }
                }
                if(!strB.toString().isEmpty())
                    StrList.add(strB.toString());
            }
            System.out.println(Arrays.toString(StrList.toArray()));
        }

使用递归的简单python解决方案。

def get_permutations(string):

    # base case
    if len(string) <= 1:
        return set([string])

    all_chars_except_last = string[:-1]
    last_char = string[-1]

    # recursive call: get all possible permutations for all chars except last
    permutations_of_all_chars_except_last = get_permutations(all_chars_except_last)

    # put the last char in all possible positions for each of the above permutations
    permutations = set()
    for permutation_of_all_chars_except_last in permutations_of_all_chars_except_last:
        for position in range(len(all_chars_except_last) + 1):
            permutation = permutation_of_all_chars_except_last[:position] + last_char + permutation_of_all_chars_except_last[position:]
            permutations.add(permutation)

    return permutations

基于Heap算法的我的实现:

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

public class PermutationString {
public static List<String> permute(char[] str, int n) {
    List<String> permutations = new ArrayList<>();
    if (n == 1) {
        permutations.add(new String(str));
    }
    else {
        for (int i = 0; i < n; i++) {
            permutations.addAll(permute(str, n-1));
            if (n % 2 == 0) {
                swap(str, i, n-1);
            }
            else {
                swap(str, 0, n-1);
            }
        }
    }
    return permutations;
}


public static void swap(char[] str, int i, int j) {
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

public static void main(String[] args) {

    List<String> permutations = permute("abcdefgh".toCharArray(), 8);

    System.out.println(permutations);

}
}

时间复杂度为O(n!* n)， O(n)为空间复杂度。