使用Set操作建模“依赖于其他选择的选择”更容易理解相关排列 使用依赖排列，可用的选择减少，因为位置被从左到右的选定字符填充。递归调用的终端条件是测试可用选择集是否为空。当满足终端条件时，置换完成，并存储到“结果”列表中。

public static List<String> stringPermutation(String s) {
    List<String> results = new ArrayList<>();
    Set<Character> charSet = s.chars().mapToObj(m -> (char) m).collect(Collectors.toSet());
    stringPermutation(charSet, "", results);
    return results;
}

private static void stringPermutation(Set<Character> charSet, 
        String prefix, List<String> results) {
    if (charSet.isEmpty()) {
        results.add(prefix);
        return;
    }
    for (Character c : charSet) {
        Set<Character> newSet = new HashSet<>(charSet);
        newSet.remove(c);
        stringPermutation(newSet, prefix + c, results);
    }
} 

该代码可以泛化为一组对象查找排列。在本例中，我使用了一组颜色。

public enum Color{
    ORANGE,RED,BULE,GREEN,YELLOW;
}

public static List<List<Color>> colorPermutation(Set<Color> colors) {
    List<List<Color>> results = new ArrayList<>();
    List<Color> prefix = new ArrayList<>();
    permutation(colors, prefix, results);
    return results;
}

private static <T> void permutation(Set<T> set, List<T> prefix, List<List<T>> results) {
    if (set.isEmpty()) {
        results.add(prefix);
        return;
    }
    for (T t : set) {
        Set<T> newSet = new HashSet<>(set);
        List<T> newPrefix = new ArrayList<>(prefix);
        newSet.remove(t);
        newPrefix.add(t);
        permutation(newSet, newPrefix, results);
    }
} 

测试代码。

public static void main(String[] args) {
    List<String> stringPerm = stringPermutation("abcde");
    System.out.println("# of permutations:" + stringPerm.size());
    stringPerm.stream().forEach(e -> System.out.println(e));

    Set<Color> colorSet = Arrays.stream(Color.values()).collect(Collectors.toSet());
    List<List<Color>> colorPerm = colorPermutation(colorSet);
    System.out.println("# of permutations:" + colorPerm.size());
    colorPerm.stream().forEach(e -> System.out.println(e));
}

这是一个C解:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>


char* addLetter(char* string, char *c) {
    char* result = malloc(sizeof(string) + 2);
    strcpy(result, string);
    strncat(result, c, 1);
    return result;
}

char* removeLetter(char* string, char *c) {
    char* result = malloc(sizeof(string));
    int j = 0;
    for (int i = 0; i < strlen(string); i++) {
        if (string[i] != *c) {
            result[j++] = string[i];
        }
    }
    result[j] = '\0';

    return result;
}

void makeAnagram(char *anagram, char *letters) {

    if (*letters == '\0') {
        printf("%s\n", anagram);
        return;
    }

    char *c = letters;
    while (*c != '\0') {
        makeAnagram(addLetter(anagram, c),
                    removeLetter(letters, c));
        c++;
    }

}

int main() {

    makeAnagram("", "computer");

    return 0;
}

Java中一个非常基本的解决方案是使用递归+设置(以避免重复)，如果你想存储和返回解决方案字符串:

public static Set<String> generatePerm(String input)
{
    Set<String> set = new HashSet<String>();
    if (input == "")
        return set;

    Character a = input.charAt(0);

    if (input.length() > 1)
    {
        input = input.substring(1);

        Set<String> permSet = generatePerm(input);

        for (String x : permSet)
        {
            for (int i = 0; i <= x.length(); i++)
            {
                set.add(x.substring(0, i) + a + x.substring(i));
            }
        }
    }
    else
    {
        set.add(a + "");
    }
    return set;
}

如果有人想要生成排列来做一些事情，而不是通过void方法打印它们:

static List<int[]> permutations(int n) {

    class Perm {
        private final List<int[]> permutations = new ArrayList<>();

        private void perm(int[] array, int step) {
            if (step == 1) permutations.add(array.clone());
            else for (int i = 0; i < step; i++) {
                perm(array, step - 1);
                int j = (step % 2 == 0) ? i : 0;
                swap(array, step - 1, j);
            }
        }

        private void swap(int[] array, int i, int j) {
            int buffer = array[i];
            array[i] = array[j];
            array[j] = buffer;
        }

    }

    int[] nVector  = new int[n];
    for (int i = 0; i < n; i++) nVector [i] = i;

    Perm perm = new Perm();
    perm.perm(nVector, n);
    return perm.permutations;

}

这是一个具有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);

}

}

下面是一个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