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

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

(通过Java编程入门)

这是一个更快的解决方案，因为它不受字符串连接计算复杂度O(n^2)的影响。另一方面它是无循环的，完全递归的

public static void main(String[] args) {
    permutation("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
}

private static void permutation(String str) {
    char[] stringArray = str.toCharArray();
    printPermutation(stringArray, 0, stringArray.length, 0, 1);
}

private static void printPermutation(char[] string, int loopCounter, int length, int indexFrom, int indexTo) {
    // Stop condition
    if (loopCounter == length)
        return;

    /* 
     When reaching the end of the array:
     1- Reset loop indices.
     2- Increase length counter. 
    */ 
    if (indexTo == length) {
        indexFrom = 0;
        indexTo = 1;
        ++loopCounter;
    }

    // Print.
    System.out.println(string);

    // Swap from / to indices.
    char temp = string[indexFrom];
    string[indexFrom] = string[indexTo];
    string[indexTo] = temp;

    // Go for next iteration.
    printPermutation(string, loopCounter, length, ++indexFrom, ++indexTo);
}

这是一个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;
}

使用递归。

当输入是空字符串时，唯一的排列就是空字符串。尝试将字符串中的每个字母作为第一个字母，然后使用递归调用找到其余字母的所有排列。

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

class Permutation {
    private static List<String> permutation(String prefix, String str) {
        List<String> permutations = new ArrayList<>();
        int n = str.length();
        if (n == 0) {
            permutations.add(prefix);
        } else {
            for (int i = 0; i < n; i++) {
                permutations.addAll(permutation(prefix + str.charAt(i), str.substring(i + 1, n) + str.substring(0, i)));
            }
        }
        return permutations;
    }

    public static void main(String[] args) {
        List<String> perms = permutation("", "abcd");

        String[] array = new String[perms.size()];
        for (int i = 0; i < perms.size(); i++) {
            array[i] = perms.get(i);
        }

        int x = array.length;

        for (final String anArray : array) {
            System.out.println(anArray);
        }
    }
}

递归是不必要的，甚至你可以直接计算任何排列，这个解决方案使用泛型来排列任何数组。

这里有关于这个algorihtm的很好的信息。

对于c#开发人员来说，这里有更有用的实现。

public static void main(String[] args) {
    String word = "12345";

    Character[] array = ArrayUtils.toObject(word.toCharArray());
    long[] factorials = Permutation.getFactorials(array.length + 1);

    for (long i = 0; i < factorials[array.length]; i++) {
        Character[] permutation = Permutation.<Character>getPermutation(i, array, factorials);
        printPermutation(permutation);
    }
}

private static void printPermutation(Character[] permutation) {
    for (int i = 0; i < permutation.length; i++) {
        System.out.print(permutation[i]);
    }
    System.out.println();
}

该算法计算每个排列的时间和空间复杂度为O(N)。

public class Permutation {
    public static <T> T[] getPermutation(long permutationNumber, T[] array, long[] factorials) {
        int[] sequence = generateSequence(permutationNumber, array.length - 1, factorials);
        T[] permutation = generatePermutation(array, sequence);

        return permutation;
    }

    public static <T> T[] generatePermutation(T[] array, int[] sequence) {
        T[] clone = array.clone();

        for (int i = 0; i < clone.length - 1; i++) {
            swap(clone, i, i + sequence[i]);
        }

        return clone;
    }

    private static int[] generateSequence(long permutationNumber, int size, long[] factorials) {
        int[] sequence = new int[size];

        for (int j = 0; j < sequence.length; j++) {
            long factorial = factorials[sequence.length - j];
            sequence[j] = (int) (permutationNumber / factorial);
            permutationNumber = (int) (permutationNumber % factorial);
        }

        return sequence;
    }

    private static <T> void swap(T[] array, int i, int j) {
        T t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static long[] getFactorials(int length) {
        long[] factorials = new long[length];
        long factor = 1;

        for (int i = 0; i < length; i++) {
            factor *= i <= 1 ? 1 : i;
            factorials[i] = factor;
        }

        return factorials;
    }
}