生成给定字符串的所有排列

Question

如何优雅地找出字符串的所有排列组合？例如，对于字符串ba，其排列组合是ba和ab，但是对于更长的字符串，比如abcdefgh，有没有Java实现的例子呢？

- GurdeepS

---

这里有很多答案：https://dev59.com/43VD5IYBdhLWcg3wXaid。 - Marek Sapota

这是一个非常流行的问题。你可以在这里看一下：http://www.careercup.com/question?id=3861299 - JJunior

需要提及一个假设，字符是唯一的。例如，对于一个字符串 "aaaa" 只有一个答案。为了得到更通用的答案，您可以将字符串保存在一个集合中以避免重复。 - Afshin Moazami

重复字符被允许吗，还是不允许重复字符？单个字符串是否可以有多个相同字符的出现？ - Anderson Green

阅读理论（或者如果像我一样懒的话，可以去http://en.wikipedia.org/wiki/Permutation），并实现一个真正的算法。基本上，您可以生成元素排序的序列（它是字符串的事实是无关紧要的），并在顺序中走过，直到回到起点。避免任何涉及递归或字符串操作的内容。 - CurtainDog

Answer 1

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编程简介获取)

- SuperJulietta

---

解决方案似乎来自于这里：http://introcs.cs.princeton.edu/java/23recursion/Permutations.java.html - cyber-monk

没什么太难的，我得出了几乎一样的答案。小改动：不必递归至 n==0，可以在 n==1 时停止并打印出 prefix + str。 - lambshaanxy

“这个算法的时间和空间复杂度是多少？” 任何输出排列的算法，如果没有某种形式的部分答案缓存，其时间复杂度为O(n!)，因为排列问题的结果集对输入进行了阶乘处理。 - jeremyjjbrown

优雅，没错。但是将解决方案转换为字符数组并进行交换以生成排列将需要更少的复制并产生更少的垃圾。此外，该算法未考虑重复字符。 - Gene

@AfshinMoazami，我认为 str.substring(i+1, n) 可以替换为 str.substring(i+1)。使用 str.substring(i) 会导致 java.lang.StackOverflowError。 - Ayusman

Answer 2

使用递归。

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

- Mark Byers

---

你如何为 permute 方法添加返回类型？编译器无法在每次迭代中确定该方法的返回类型，尽管显然它是一个字符串类型。 - user1712095

你如何确保在这种方法中有不同的排列？ - kapad

Answer 3

这是我的解决方案，它基于书籍《Cracking the Coding Interview》（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" 的运行结果:

• 步骤1：合并 [a] 和 b: [ba, ab]

• 步骤2：合并 [ba, ab] 和 c: [cba, bca, bac, cab, acb, abc]

• 步骤3：合并 [cba, bca, bac, cab, acb, abc] 和 d: [dcba, cdba, cbda, cbad, dbca, bdca, bcda, bcad, dbac, bdac, badc, bacd, dcab, cdab, cadb, cabd, dacb, adcb, acdb, acbd, dabc, adbc, abdc, abcd]

- jeantimex

---

《破解程序员面试：代码之美》第六版第71页。 :) - KarimIhab

这真的是一个好的解决方案吗？它依赖于将结果存储在一个列表中，因此对于短输入字符串来说，它会失控地增长。 - Androrider

合并（Merge）是什么？ - Basavaraj Walikar

它将字符c插入到列表中每个字符串的所有可能位置。 例如，如果列表只包含["b"]，并且字符c是"a"，则合并结果为["ab", "ba"]。以下是Swift版本的相同解决方案 https://gist.github.com/daniaDlbani/3bc10e02541f9ba310d546040c5322fc - Dania Delbani

StringBuffer是线程安全的，但会带来一定的开销。对于只有一个线程的情况，请使用StringBuilder。 - dimirsen Z

Answer 4

在这里和其他论坛中提供的所有解决方案中，我最喜欢Mark Byers的解决方案。这个描述实际上让我思考并自己编写代码。 很遗憾，我无法投票支持他的解决方案，因为我是新手。
不管怎样，这是我根据他的描述实现的代码。

public class PermTest {

    public static void main(String[] args) throws Exception {
        String str = "abcdef";
        StringBuffer strBuf = new StringBuffer(str);
        doPerm(strBuf,0);
    }

    private static void doPerm(StringBuffer str, int index){

        if(index == str.length())
            System.out.println(str);            
        else { //recursively solve this by placing all other chars at current first pos
            doPerm(str, index+1);
            for (int i = index+1; i < str.length(); i++) {//start swapping all other chars with current first char
                swap(str,index, i);
                doPerm(str, index+1);
                swap(str,i, index);//restore back my string buffer
            }
        }
    }

    private  static void swap(StringBuffer str, int pos1, int pos2){
        char t1 = str.charAt(pos1);
        str.setCharAt(pos1, str.charAt(pos2));
        str.setCharAt(pos2, t1);
    }
}   

我更喜欢这个解决方案，因为它使用了StringBuffer。虽然我的解决方案在system.out.println中调用了StringBuffer的toString()方法，实际上也创建了临时字符串，但我仍然认为这比第一个解决方案更好，因为第一个解决方案创建了太多的字符串常量。也许有些性能专家可以从"内存"的角度评估一下这个解决方案（对于"时间"来说，由于额外的"swap"已经滞后了）

- srikanth yaradla

---

为什么不直接使用 if(index == str.length()) 和 doPerm(str, index + 1); 呢？这里的 currPos 似乎是不必要的。 - Robur_131

抱歉，您能详细说明一下问题吗？如果不是这样，请粘贴您建议的解决方案以供查看。您提到的currPos变量是因为多次出现和可读性而使用的额外变量，您是否建议不使用它？ - srikanth yaradla

啊，我明白你的意思了，你是指使用正向索引更改基本条件。这个方法很好用。只是我提出的解决方案大多受到其他解决方案的影响，这些解决方案通常传递截断后的字符串而不是原始字符串（在这种情况下，0是有意义的）。无论如何，感谢你的指出。我会看看是否可以编辑，因为我已经好几年没有登录这个网站了。 - srikanth yaradla

Answer 5

如果您想要存储并返回解决方案字符串，Java中一种非常基本的解决方案是使用递归+ Set（以避免重复）：

public static Set<String> generatePerm(String input)
{
    Set<String> set = new HashSet<String>();
    if (input == "")
        return set;

    Character a = input.charAt(0);

    if (input.length() > 1)
    {
        input = input.substring(1);

        Set<String> permSet = generatePerm(input);

        for (String x : permSet)
        {
            for (int i = 0; i <= x.length(); i++)
            {
                set.add(x.substring(0, i) + a + x.substring(i));
            }
        }
    }
    else
    {
        set.add(a + "");
    }
    return set;
}

- devastator

---

这个算法的时间复杂度是多少？ - ashisahu

@ashisahu，因为在给定长度为n的字符串中有n!种排列，所以时间复杂度为O(n!)。 - Zok

Answer 6

之前的贡献者已经很好地解释和提供了代码。我认为我也应该分享这种方法，因为它可能也会对某些人有帮助。这个解决方案基于(Heap算法)。

几件事情:

1. 请注意，表格中显示的最后一项只是为了帮助您更好地可视化逻辑。因此，如果我们要运行代码，最后一列中的实际值将为2,1,0（因为我们正在处理数组，而数组从0开始）。

2. 交换算法基于当前位置的偶数或奇数值进行。如果你看一下在哪里调用了交换方法，就可以很容易地理解发生了什么。

以下是发生的情况:

public static void main(String[] args) {

        String ourword = "abc";
        String[] ourArray = ourword.split("");
        permute(ourArray, ourArray.length);

    }

    private static void swap(String[] ourarray, int right, int left) {
        String temp = ourarray[right];
        ourarray[right] = ourarray[left];
        ourarray[left] = temp;
    }

    public static void permute(String[] ourArray, int currentPosition) {
        if (currentPosition == 1) {
            System.out.println(Arrays.toString(ourArray));
        } else {
            for (int i = 0; i < currentPosition; i++) {
                // subtract one from the last position (here is where you are
                // selecting the the next last item 
                permute(ourArray, currentPosition - 1);

                // if it's odd position
                if (currentPosition % 2 == 1) {
                    swap(ourArray, 0, currentPosition - 1);
                } else {
                    swap(ourArray, i, currentPosition - 1);
                }
            }
        }
    }

- grepit

Answer 7

让我们以输入abc为例。

首先从集合中最后一个元素（c）开始，将第二个最后的元素（b）添加到其前面、末尾和每个可能的中间位置，使其变为["bc", "cb"]，然后以相同的方式将从后面添加的下一个元素（a）添加到集合中的每个字符串中，使其变为：

"a" + "bc" = ["abc", "bac", "bca"]  and  "a" + "cb" = ["acb" ,"cab", "cba"] 

因此，整个排列组合：

["abc", "bac", "bca","acb" ,"cab", "cba"]

代码：

public class Test 
{
    static Set<String> permutations;
    static Set<String> result = new HashSet<String>();

    public static Set<String> permutation(String string) {
        permutations = new HashSet<String>();

        int n = string.length();
        for (int i = n - 1; i >= 0; i--) 
        {
            shuffle(string.charAt(i));
        }
        return permutations;
    }

    private static void shuffle(char c) {
        if (permutations.size() == 0) {
            permutations.add(String.valueOf(c));
        } else {
            Iterator<String> it = permutations.iterator();
            for (int i = 0; i < permutations.size(); i++) {

                String temp1;
                for (; it.hasNext();) {
                    temp1 = it.next();
                    for (int k = 0; k < temp1.length() + 1; k += 1) {
                        StringBuilder sb = new StringBuilder(temp1);

                        sb.insert(k, c);

                        result.add(sb.toString());
                    }
                }
            }
            permutations = result;
            //'result' has to be refreshed so that in next run it doesn't contain stale values.
            result = new HashSet<String>();
        }
    }

    public static void main(String[] args) {
        Set<String> result = permutation("abc");

        System.out.println("\nThere are total of " + result.size() + " permutations:");
        Iterator<String> it = result.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

- Vihaan Verma

---

我喜欢你的解决方案。非常直观且解释清晰。非常感谢你。 - Samy Boulos

Answer 8

这个没有递归。

public static void permute(String s) {
    if(null==s || s.isEmpty()) {
        return;
    }

    // List containing words formed in each iteration 
    List<String> strings = new LinkedList<String>();
    strings.add(String.valueOf(s.charAt(0))); // add the first element to the list

     // Temp list that holds the set of strings for 
     //  appending the current character to all position in each word in the original list
    List<String> tempList = new LinkedList<String>(); 

    for(int i=1; i< s.length(); i++) {

        for(int j=0; j<strings.size(); j++) {
            tempList.addAll(merge(s.charAt(i), strings.get(j)));
                        }
        strings.removeAll(strings);
        strings.addAll(tempList);

        tempList.removeAll(tempList);

    }

    for(int i=0; i<strings.size(); i++) {
        System.out.println(strings.get(i));
    }
}

/**
 * helper method that appends the given character at each position in the given string 
 * and returns a set of such modified strings 
 * - set removes duplicates if any(in case a character is repeated)
 */
private static Set<String> merge(Character c,  String s) {
    if(s==null || s.isEmpty()) {
        return null;
    }

    int len = s.length();
    StringBuilder sb = new StringBuilder();
    Set<String> list = new HashSet<String>();

    for(int i=0; i<= len; i++) {
        sb = new StringBuilder();
        sb.append(s.substring(0, i) + c + s.substring(i, len));
        list.add(sb.toString());
    }

    return list;
}

- Jeya

---

这个解决方案似乎是错误的 System.out.println(permute("AABBC").size()); 显示为45，但实际上5！= 120。 - Mladen Adamovic

Answer 9

这里有一种优雅的、非递归的 O(n!) 解决方案：

public static StringBuilder[] permutations(String s) {
        if (s.length() == 0)
            return null;
        int length = fact(s.length());
        StringBuilder[] sb = new StringBuilder[length];
        for (int i = 0; i < length; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int times = length / (i + 1);
            for (int j = 0; j < times; j++) {
                for (int k = 0; k < length / times; k++) {
                    sb[j * length / times + k].insert(k, ch);
                }
            }
        }
        return sb;
    }

- Adilli Adil

---

如果单词少于4个字母，则此解决方案有效，否则，结果数组的一半仅包含唯一的单词。 - Maksim Maksimov

Answer 10

Python实现

def getPermutation(s, prefix=''):
        if len(s) == 0:
                print prefix
        for i in range(len(s)):
                getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] )



getPermutation('abcd','')

- riteshkasat