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

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

示例:取输入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
    }
}

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

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')

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

使用递归。

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

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

使用递归。

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