没有递归的Java实现

public Set<String> permutate(String s){
    Queue<String> permutations = new LinkedList<String>();
    Set<String> v = new HashSet<String>();
    permutations.add(s);

    while(permutations.size()!=0){
        String str = permutations.poll();
        if(!v.contains(str)){
            v.add(str);
            for(int i = 0;i<str.length();i++){
                String c = String.valueOf(str.charAt(i));
                permutations.add(str.substring(i+1) + c +  str.substring(0,i));
            }
        }
    }
    return v;
}

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

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

/** Returns an array list containing all
 * permutations of the characters in s. */
public static ArrayList<String> permute(String s) {
    ArrayList<String> perms = new ArrayList<>();
    int slen = s.length();
    if (slen > 0) {
        // Add the first character from s to the perms array list.
        perms.add(Character.toString(s.charAt(0)));

        // Repeat for all additional characters in s.
        for (int i = 1;  i < slen;  ++i) {

            // Get the next character from s.
            char c = s.charAt(i);

            // For each of the strings currently in perms do the following:
            int size = perms.size();
            for (int j = 0;  j < size;  ++j) {

                // 1. remove the string
                String p = perms.remove(0);
                int plen = p.length();

                // 2. Add plen + 1 new strings to perms.  Each new string
                //    consists of the removed string with the character c
                //    inserted into it at a unique location.
                for (int k = 0;  k <= plen;  ++k) {
                    perms.add(p.substring(0, k) + c + p.substring(k));
                }
            }
        }
    }
    return perms;
}

基于Mark Byers的回答，我的python实现:

def permutations(string):
    if len(string) == 1:
        return [string]
    permutations=[]
    for i in range(len(string)):
        for perm in permutations(string[:i]+string[i+1:]):
            permutations.append(string[i] + perm)
    return permutations

我定义了左右两个字符串。一开始，左边是输入字符串，右边是“”。我递归地从左边选择所有可能的字符，并将其添加到右边的末尾。然后，在left-charAt(I)和right+charAt(I)上调用递归函数。我定义了一个类来跟踪生成的排列。

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

public class FindPermutations {

    static class Permutations {
        Set<String> permutations = new HashSet<>();
    }

    /**
     * Building all the permutations by adding chars of left to right one by one.
     *
     * @param left         The left string
     * @param right        The right string
     * @param permutations The permutations
     */
    private void findPermutations(String left, String right, Permutations permutations) {
        int n = left.length();
        if (n == 0) {
            permutations.permutations.add(right);
        }
        for (int i = 0; i < n; i++) {
            findPermutations(left.substring(0, i) + left.substring(i + 1, n), right + left.charAt(i), permutations);
        }
    }

    /**
     * Gets all the permutations of a string s.
     *
     * @param s The input string
     * @return all the permutations of a string s
     */
    public Permutations getPermutations(String s) {
        Permutations permutations = new Permutations();
        findPermutations(s, "", permutations);
        return permutations;
    }

    public static void main(String[] args) {
        FindPermutations findPermutations = new FindPermutations();
        String s = "ABC";
        Permutations permutations = findPermutations.getPermutations(s);
        printPermutations(permutations);
    }

    private static void printPermutations(Permutations permutations) {
        for (String p : permutations.permutations) {
            System.out.println(p);
        }
    }

}

我希望这能有所帮助。

倒计时Quickperm算法的通用实现，表示#1(可伸缩，非递归)。

/**
 * Generate permutations based on the
 * Countdown <a href="http://quickperm.org/">Quickperm algorithm</>.
 */
public static <T> List<List<T>> generatePermutations(List<T> list) {
    List<T> in = new ArrayList<>(list);
    List<List<T>> out = new ArrayList<>(factorial(list.size()));

    int n = list.size();
    int[] p = new int[n +1];
    for (int i = 0; i < p.length; i ++) {
        p[i] = i;
    }
    int i = 0;
    while (i < n) {
        p[i]--;
        int j = 0;
        if (i % 2 != 0) { // odd?
            j = p[i];
        }
        // swap
        T iTmp = in.get(i);
        in.set(i, in.get(j));
        in.set(j, iTmp);

        i = 1;
        while (p[i] == 0){
            p[i] = i;
            i++;
        }
        out.add(new ArrayList<>(in));
    }
    return out;
}

private static int factorial(int num) {
    int count = num;
    while (num != 1) {
        count *= --num;
    }
    return count;
}

它需要list，因为泛型不能很好地使用数组。