没有重复的字符串排列 [英] Permutations of a string with no duplicates

问题描述

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

I read solutions to the problem of generating all the permutations of a string (solution).

谁能解释perm2与perm1有何不同？ （我觉得唯一的区别是perm1尝试将每个元素放在第一个位置，而perm2放在最后一个）

Can anyone explain how perm2 is different from perm1? (I feel the only difference is that perm1 tries to put each element in the first position while perm2 in the last one)

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

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

Also, if some letters are the same in the string, then some permutations will be the same? The only way I can think of to prevent this is to save the result in a hashset so as to keep only one instance of a permutation. Is there a better solution?

推荐答案

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

I expect that the justification for the second solution is efficiency. It uses character arrays rather than String objects and swaps characters at each step rather than creating a new String via concatenation.

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

In terms of functionality the only difference between the two solutions is the order in which the results will be output.

如果输入中存在某些重复的字符，这不能保证唯一的解决方案。存储结果和检查唯一性（通过使用Set或直接通过包含）是避免这种情况的最简单方法（如果需要）。

You are correct that this does not guarantee unique solutions if there are some duplicate characters in the input. Storing the results and checking uniqueness (by using a Set or directly via contains) would be the easiest way to avoid this if required.

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

An alternative, in the second solution, would be to check if a character has already been handled. This would avoid the overhead of storing a result set (which could be significant for long strings).

第二秒 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);
    }
}

这篇关于没有重复的字符串排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！