基于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)为空间复杂度。

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class hello {
    public static void main(String[] args) throws IOException {
        hello h = new hello();
        h.printcomp();
    }
      int fact=1;
    public void factrec(int a,int k){
        if(a>=k)
        {fact=fact*k;
        k++;
        factrec(a,k);
        }
        else
        {System.out.println("The string  will have "+fact+" permutations");
        }
        }
    public void printcomp(){
        String str;
        int k;
        Scanner in = new Scanner(System.in);
        System.out.println("enter the string whose permutations has to b found");
        str=in.next();
        k=str.length();
        factrec(k,1);
        String[] arr =new String[fact];
        char[] array = str.toCharArray();
        while(p<fact)
        printcomprec(k,array,arr);
            // if incase u need array containing all the permutation use this
            //for(int d=0;d<fact;d++)         
        //System.out.println(arr[d]);
    }
    int y=1;
    int p = 0;
    int g=1;
    int z = 0;
    public void printcomprec(int k,char array[],String arr[]){
        for (int l = 0; l < k; l++) {
            for (int b=0;b<k-1;b++){
            for (int i=1; i<k-g; i++) {
                char temp;
                String stri = "";
                temp = array[i];
                array[i] = array[i + g];
                array[i + g] = temp;
                for (int j = 0; j < k; j++)
                    stri += array[j];
                arr[z] = stri;
                System.out.println(arr[z] + "   " + p++);
                z++;
            }
            }
            char temp;
            temp=array[0];
            array[0]=array[y];
            array[y]=temp;
            if (y >= k-1)
                y=y-(k-1);
            else
                y++;
        }
        if (g >= k-1)
            g=1;
        else
            g++;
    }

}

使用位操作可以很容易地做到这一点。“我们都知道，任何给定的有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()));
        }

我的实现基于Mark Byers上面的描述:

    static Set<String> permutations(String str){
        if (str.isEmpty()){
            return Collections.singleton(str);
        }else{
            Set <String> set = new HashSet<>();
            for (int i=0; i<str.length(); i++)
                for (String s : permutations(str.substring(0, i) + str.substring(i+1)))
                    set.add(str.charAt(i) + s);
            return set;
        }
    }

这可以通过简单地在前面部分结果的所有位置依次插入字符串的每个字母来迭代完成。

我们以[A]开头，与B连成[BA, AB]，与C连成[CBA, BCA, BAC, CAB等]。

运行时间将是O(n!)，对于测试用例ABCD，它是1 x 2 x 3 x 4。

在上面的乘积中，1是A, 2是B，以此类推。

飞镖示例:

void main() {

  String insertAt(String a, String b, int index)
  {
    return a.substring(0, index) + b + a.substring(index);
  }

  List<String> Permute(String word) {

    var letters = word.split('');

    var p_list = [ letters.first ];

    for (var c in letters.sublist(1)) {

      var new_list = [ ];

      for (var p in p_list)
        for (int i = 0; i <= p.length; i++)
          new_list.add(insertAt(p, c, i));

      p_list = new_list;
    }

    return p_list;
  }

  print(Permute("ABCD"));

}

python实现

def getPermutation(s, prefix=''):
        if len(s) == 0:
                print prefix
        for i in range(len(s)):
                getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] )



getPermutation('abcd','')