这是一个具有O(n!)时间复杂度的算法，具有纯递归和直观。

public class words {
static String combinations;
public static List<String> arrlist=new ArrayList<>();
public static void main(String[] args) {
    words obj = new words();

    String str="premandl";
    obj.getcombination(str, str.length()-1, "");
    System.out.println(arrlist);

}


public void getcombination(String str, int charIndex, String output) {

    if (str.length() == 0) {
        arrlist.add(output);
        return ;
    }

    if (charIndex == -1) {
        return ;
    }

    String character = str.toCharArray()[charIndex] + "";
    getcombination(str, --charIndex, output);

    String remaining = "";

    output = output + character;

    remaining = str.substring(0, charIndex + 1) + str.substring(charIndex + 2);

    getcombination(remaining, remaining.length() - 1, output);

}

}

使用递归的简单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

这个没有递归

public static void permute(String s) {
    if(null==s || s.isEmpty()) {
        return;
    }

    // List containing words formed in each iteration 
    List<String> strings = new LinkedList<String>();
    strings.add(String.valueOf(s.charAt(0))); // add the first element to the list

     // Temp list that holds the set of strings for 
     //  appending the current character to all position in each word in the original list
    List<String> tempList = new LinkedList<String>(); 

    for(int i=1; i< s.length(); i++) {

        for(int j=0; j<strings.size(); j++) {
            tempList.addAll(merge(s.charAt(i), strings.get(j)));
                        }
        strings.removeAll(strings);
        strings.addAll(tempList);

        tempList.removeAll(tempList);

    }

    for(int i=0; i<strings.size(); i++) {
        System.out.println(strings.get(i));
    }
}

/**
 * helper method that appends the given character at each position in the given string 
 * and returns a set of such modified strings 
 * - set removes duplicates if any(in case a character is repeated)
 */
private static Set<String> merge(Character c,  String s) {
    if(s==null || s.isEmpty()) {
        return null;
    }

    int len = s.length();
    StringBuilder sb = new StringBuilder();
    Set<String> list = new HashSet<String>();

    for(int i=0; i<= len; i++) {
        sb = new StringBuilder();
        sb.append(s.substring(0, i) + c + s.substring(i, len));
        list.add(sb.toString());
    }

    return list;
}

下面是一个java实现:

/* All Permutations of a String */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Complexity O(n*n!) */
class Ideone
{
     public static ArrayList<String> strPerm(String str, ArrayList<String> list)
     {
        int len = str.length();
        if(len==1){
            list.add(str);
            return list;
        }

        list = strPerm(str.substring(0,len-1),list);
        int ls = list.size();
        char ap = str.charAt(len-1);
        for(int i=0;i<ls;i++){
            String temp = list.get(i);
            int tl = temp.length();
            for(int j=0;j<=tl;j++){
                list.add(temp.substring(0,j)+ap+temp.substring(j,tl));  
            }
        }

        while(true){
            String temp = list.get(0);
            if(temp.length()<len)
                list.remove(temp);
            else
                break;
        }

        return list;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        String str = "abc";
        ArrayList<String> list = new ArrayList<>();

        list = strPerm(str,list);
        System.out.println("Total Permutations : "+list.size());
        for(int i=0;i<list.size();i++)
            System.out.println(list.get(i));

    }
}

http://ideone.com/nWPb3k

/** Returns an array list containing all
 * permutations of the characters in s. */
public static ArrayList<String> permute(String s) {
    ArrayList<String> perms = new ArrayList<>();
    int slen = s.length();
    if (slen > 0) {
        // Add the first character from s to the perms array list.
        perms.add(Character.toString(s.charAt(0)));

        // Repeat for all additional characters in s.
        for (int i = 1;  i < slen;  ++i) {

            // Get the next character from s.
            char c = s.charAt(i);

            // For each of the strings currently in perms do the following:
            int size = perms.size();
            for (int j = 0;  j < size;  ++j) {

                // 1. remove the string
                String p = perms.remove(0);
                int plen = p.length();

                // 2. Add plen + 1 new strings to perms.  Each new string
                //    consists of the removed string with the character c
                //    inserted into it at a unique location.
                for (int k = 0;  k <= plen;  ++k) {
                    perms.add(p.substring(0, k) + c + p.substring(k));
                }
            }
        }
    }
    return perms;
}

import java.io.*;
public class Anagram {

public static void main(String[] args) {
      java.util.Scanner sc=new java.util.Scanner(System.in);
            PrintWriter p=new PrintWriter(System.out,true);
            p.println("Enter Word");
            String a[],s="",st;boolean flag=true;
            int in[],n,nf=1,i,j=0,k,m=0;
            char l[];
            st=sc.next();
            p.println("Anagrams");
            p.println("1 . "+st);
            l=st.toCharArray();
            n=st.length();
            for(i=1;i<=n;i++){
                nf*=i;
            }

            i=1;
            a=new String[nf];
            in=new int[n];
            a[0]=st;
            while(i<nf){
                for(m=0;m<n;m++){
                    in[m]=n;
                }j=0;
                while(j<n){
                    k=(int)(n*Math.random());

                    for(m=0;m<=j;m++){
                        if(k==in[m]){
                            flag=false;
                            break;          
                        }
                    }
                    if(flag==true){
                        in[j++]=k;
                    }flag=true;
                }s="";
                for(j=0;j<n;j++){
                    s+=l[in[j]];
                }

                //Removing same words
                for(m=0;m<=i;m++){
                        if(s.equalsIgnoreCase(a[m])){
                            flag=false;
                            break;          
                        }
                    }
                    if(flag==true){
                        a[i++]=s;
                        p.println(i+" . "+a[i-1]);
                    }flag=true;

            }

    }
}