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

这里有关于这个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;
    }
}

递归Python解决方案

def permute(input_str):
    _permute("", input_str)

def _permute(prefix, str_to_permute):
    if str_to_permute == '':
        print(prefix)

    else:
        for i in range(len(str_to_permute)): 
            _permute(prefix+str_to_permute[i], str_to_permute[0:i] + str_to_permute[i+1:])

if __name__ == '__main__':
    permute('foobar')

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++;
    }

}

//Rotate and create words beginning with all letter possible and push to stack 1

//Read from stack1 and for each word create words with other letters at the next location by rotation and so on 

/*  eg : man

    1. push1 - man, anm, nma
    2. pop1 - nma ,  push2 - nam,nma
       pop1 - anm ,  push2 - amn,anm
       pop1 - man ,  push2 - mna,man
*/

public class StringPermute {

    static String str;
    static String word;
    static int top1 = -1;
    static int top2 = -1;
    static String[] stringArray1;
    static String[] stringArray2;
    static int strlength = 0;

    public static void main(String[] args) throws IOException {
        System.out.println("Enter String : ");
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader bfr = new BufferedReader(isr);
        str = bfr.readLine();
        word = str;
        strlength = str.length();
        int n = 1;
        for (int i = 1; i <= strlength; i++) {
            n = n * i;
        }
        stringArray1 = new String[n];
        stringArray2 = new String[n];
        push(word, 1);
        doPermute();
        display();
    }

    public static void push(String word, int x) {
        if (x == 1)
            stringArray1[++top1] = word;
        else
            stringArray2[++top2] = word;
    }

    public static String pop(int x) {
        if (x == 1)
            return stringArray1[top1--];
        else
            return stringArray2[top2--];
    }

    public static void doPermute() {

        for (int j = strlength; j >= 2; j--)
            popper(j);

    }

    public static void popper(int length) {
        // pop from stack1 , rotate each word n times and push to stack 2
        if (top1 > -1) {
            while (top1 > -1) {
                word = pop(1);
                for (int j = 0; j < length; j++) {
                    rotate(length);
                    push(word, 2);
                }
            }
        }
        // pop from stack2 , rotate each word n times w.r.t position and push to
        // stack 1
        else {
            while (top2 > -1) {
                word = pop(2);
                for (int j = 0; j < length; j++) {
                    rotate(length);
                    push(word, 1);
                }
            }
        }

    }

    public static void rotate(int position) {
        char[] charstring = new char[100];
        for (int j = 0; j < word.length(); j++)
            charstring[j] = word.charAt(j);

        int startpos = strlength - position;
        char temp = charstring[startpos];
        for (int i = startpos; i < strlength - 1; i++) {
            charstring[i] = charstring[i + 1];
        }
        charstring[strlength - 1] = temp;
        word = new String(charstring).trim();
    }

    public static void display() {
        int top;
        if (top1 > -1) {
            while (top1 > -1)
                System.out.println(stringArray1[top1--]);
        } else {
            while (top2 > -1)
                System.out.println(stringArray2[top2--]);
        }
    }
}

如果有人想要生成排列来做一些事情，而不是通过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;

}

使用递归。

依次尝试每个字母作为第一个字母，然后使用递归调用找到剩余字母的所有排列。 基本情况是，当输入是空字符串时，唯一的排列就是空字符串。