java - 不重复的字符串的排列

Question

我阅读了生成字符串所有排列 (solution) 问题的解决方案。

谁能解释一下 perm2 与 perm1 有何不同？ (我觉得唯一的区别是perm1试图把每个元素放在第一个位置，而perm2放在最后一个)

// print N! permutation of the characters of the string s (in order)
public  static void perm1(String s) { perm1("", s); }
private static void perm1(String prefix, String s) {
    int N = s.length();
    if (N == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < N; i++)
           perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
    }

}

 // print N! permutation of the elements of array a (not in order)
    public static void perm2(String s) {
       int N = s.length();
       char[] a = new char[N];
       for (int i = 0; i < N; i++)
           a[i] = s.charAt(i);
       perm2(a, N);
    }

    private static void perm2(char[] a, int n) {
        if (n == 1) {
            System.out.println(a);
            return;
        }
        for (int i = 0; i < n; i++) {
            swap(a, i, n-1);
            perm2(a, n-1);
            swap(a, i, n-1);
        }
    }

另外，如果字符串中某些字母相同，那么某些排列也会相同？我能想到的防止这种情况的唯一方法是将结果保存在哈希集中，以便只保留一个排列实例。有更好的解决方案吗？

Answer 1

我希望第二种解决方案的理由是效率。它使用字符数组而不是 String 对象，并在每一步交换字符，而不是通过连接创建新的 String。

就功能而言，两种解决方案之间的唯一区别是结果输出的顺序。

你是对的，如果输入中有一些重复的字符，这并不能保证唯一的解决方案。如果需要，存储结果和检查唯一性(通过使用 Set 或直接通过 contains)将是避免这种情况的最简单方法。

在第二种解决方案中，另一种方法是检查字符是否已被处理。这将避免存储结果集的开销(这对于长字符串可能很重要)。

在第二个 perm2 函数中:

if (n == 1) {
    System.out.println(a);
    return;
}
for (int i = n; i < a.length; i++) {
    if (a[i] == a[n-1])
        return;
}
for (int i = 0; i < n; i++) {
    boolean duplicate = false;
    for (int j = 0; !duplicate && j < i; j++)
        duplicate = a[i] == a[j];
    if (!duplicate) {
        swap(a, i, n-1);
        perm2(a, n-1);
        swap(a, i, n-1);
    }
}