我一直在学习递归思考，第一个打动我的自然解决方案如下。一个更简单的问题是找到一个短一个字母的字符串的排列。我将假设，并相信我的每一根纤维，我的函数可以正确地找到一个字符串的排列，比我目前正在尝试的字符串短一个字母。

Given a string say 'abc', break it into a subproblem of finding permutations of a string one character less which is 'bc'. Once we have permutations of 'bc' we need to know how to combine it with 'a' to get the permutations for 'abc'. This is the core of recursion. Use the solution of a subproblem to solve the current problem. By observation, we can see that inserting 'a' in all the positions of each of the permutations of 'bc' which are 'bc' and 'cb' will give us all the permutations of 'abc'. We have to insert 'a' between adjacent letters and at the front and end of each permutation. For example

我们有bc

“a”+“bc”=“abc”

“b”+“a”+“c”=“bac”

“b”+“a”=“b”

对于'cb'我们有

a + b = acb

“c”+“a”+“b”=“cab”

“cb”+“a”=“cb”

下面的代码片段将说明这一点。下面是该代码片段的工作链接。

def main():
    result = []
    for permutation in ['bc', 'cb']:
        for i in range(len(permutation) + 1):
            result.append(permutation[:i] + 'a' + permutation[i:])
    return result


if __name__ == '__main__':
    print(main())

完整的递归解将是。下面是完整代码的工作链接。

def permutations(s):
    if len(s) == 1 or len(s) == 0:
        return s
    _permutations = []
    for permutation in permutations(s[1:]):
        for i in range(len(permutation) + 1):
            _permutations.append(permutation[:i] + s[0] + permutation[i:])
    return _permutations


def main(s):
    print(permutations(s))


if __name__ == '__main__':
    main('abc')

以下是我在《破解编程面试》(P54)一书中提出的解决方案:

/**
 * List permutations of a string.
 * 
 * @param s the input string
 * @return  the list of permutations
 */
public static ArrayList<String> permutation(String s) {
    // The result
    ArrayList<String> res = new ArrayList<String>();
    // If input string's length is 1, return {s}
    if (s.length() == 1) {
        res.add(s);
    } else if (s.length() > 1) {
        int lastIndex = s.length() - 1;
        // Find out the last character
        String last = s.substring(lastIndex);
        // Rest of the string
        String rest = s.substring(0, lastIndex);
        // Perform permutation on the rest string and
        // merge with the last character
        res = merge(permutation(rest), last);
    }
    return res;
}

/**
 * @param list a result of permutation, e.g. {"ab", "ba"}
 * @param c    the last character
 * @return     a merged new list, e.g. {"cab", "acb" ... }
 */
public static ArrayList<String> merge(ArrayList<String> list, String c) {
    ArrayList<String> res = new ArrayList<>();
    // Loop through all the string in the list
    for (String s : list) {
        // For each string, insert the last character to all possible positions
        // and add them to the new list
        for (int i = 0; i <= s.length(); ++i) {
            String ps = new StringBuffer(s).insert(i, c).toString();
            res.add(ps);
        }
    }
    return res;
}

字符串"abcd"的运行输出:

第一步:合并[a]和b: [ba, ab] 步骤2:Merge [ba, ab]和c: [cba, bca, bac, cab, acb, abc] 第三步:Merge [cba, bca, bac, cab, acb, abc]和d: [dcba, cdba, cbad, cbca, bdcad

我们可以用阶乘来计算有多少字符串以某个字母开头。

示例:取输入abcd。(3!) == 6个字符串将以abcd中的每个字母开头。

static public int facts(int x){
    int sum = 1;
    for (int i = 1; i < x; i++) {
        sum *= (i+1);
    }
    return sum;
}

public static void permutation(String str) {
    char[] str2 = str.toCharArray();
    int n = str2.length;
    int permutation = 0;
    if (n == 1) {
        System.out.println(str2[0]);
    } else if (n == 2) {
        System.out.println(str2[0] + "" + str2[1]);
        System.out.println(str2[1] + "" + str2[0]);
    } else {
        for (int i = 0; i < n; i++) {
            if (true) {
                char[] str3 = str.toCharArray();
                char temp = str3[i];
                str3[i] = str3[0];
                str3[0] = temp;
                str2 = str3;
            }

            for (int j = 1, count = 0; count < facts(n-1); j++, count++) {
                if (j != n-1) {
                    char temp1 = str2[j+1];
                    str2[j+1] = str2[j];
                    str2[j] = temp1;
                } else {
                    char temp1 = str2[n-1];
                    str2[n-1] = str2[1];
                    str2[1] = temp1;
                    j = 1;
                } // end of else block
                permutation++;
                System.out.print("permutation " + permutation + " is   -> ");
                for (int k = 0; k < n; k++) {
                    System.out.print(str2[k]);
                } // end of loop k
                System.out.println();
            } // end of loop j
        } // end of loop i
    }
}

一个java实现打印给定字符串的所有排列，考虑重复字符，只打印唯一字符，如下所示:

import java.util.Set;
import java.util.HashSet;

public class PrintAllPermutations2
{
    public static void main(String[] args)
    {
        String str = "AAC";

    PrintAllPermutations2 permutation = new PrintAllPermutations2();

    Set<String> uniqueStrings = new HashSet<>();

    permutation.permute("", str, uniqueStrings);
}

void permute(String prefixString, String s, Set<String> set)
{
    int n = s.length();

    if(n == 0)
    {
        if(!set.contains(prefixString))
        {
            System.out.println(prefixString);
            set.add(prefixString);
        }
    }
    else
    {
        for(int i=0; i<n; i++)
        {
            permute(prefixString + s.charAt(i), s.substring(0,i) + s.substring(i+1,n), set);
        }
    }
}
}

作为Python生成器，带有现代类型提示:

from typing import Iterator


def permutations(string: str, prefix: str = '') -> Iterator[str]:
    if len(string) == 0:
        yield prefix
    for i, character in enumerate(string):
        yield from permutations(string[:i] + string[i + 1:], prefix + character)


for p in permutations('abcd'):
    print(p)

这对我很有效。

import java.util.Arrays;

public class StringPermutations{
    public static void main(String args[]) {
        String inputString = "ABC";
        permute(inputString.toCharArray(), 0, inputString.length()-1);
    }

    public static void permute(char[] ary, int startIndex, int endIndex) {
        if(startIndex == endIndex){
            System.out.println(String.valueOf(ary));
        }else{
            for(int i=startIndex;i<=endIndex;i++) {
                 swap(ary, startIndex, i );
                 permute(ary, startIndex+1, endIndex);
                 swap(ary, startIndex, i );
            }
        }
    }

    public static void swap(char[] ary, int x, int y) {
        char temp = ary[x];
        ary[x] = ary[y];
        ary[y] = temp;
    }
}