java - 没有重复元素的字符串排列

Question

我正在使用此代码 https://stackoverflow.com/a/4240323/2655623创建排列并对每个结果进行一些计算。

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();

    int p = prefix.length();
    if(p==5){
            //do some calculation for |prefix| = 5
            return;
    }
    for (int i = 0; i < n; i++){
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

这个算法对我来说非常有用。但是，我想看看如何删除重复的字符，这样我就不用再计算前缀了。例如对于

permutation("aacccbbdeeeef");

我将处理 abcde 关于

A = 2 * 4*3*2*1 when a----
B = 2 * 4*3*2*1 when b----
C = 3 * 4*3*2*1 when c----
and so on...
// I hope you get the idea

不知能否减少重复计算量。

我想到的一种方法是对字符顺序进行排序，并且在我对它们使用 FOR 时只计算每个重复字符中的一个。

for (int i = 0; i < n; i++){
    if(i>0 && str.charAt(i) == str.charAt(i-1)) continue;
    permutation.....
}

这对我来说效果很好，因为只需要排列一次。当重复字母的数量很高时，它会大大减少调用次数。

现在，总结一下，我想知道是否

1. 这是我不会错过任何排列的保证吗？
2. 如何防止像 a(1)ba(2)cd 和 a(2)ba(1)cd 这样的情况发生当 p=5 时发生。至于 p=8 或 10，我使用的技巧不会那么有效。那我需要做什么？

非常感谢。

Answer 1

1. is this guarantee than I will not miss any permutation?

是的。如果所有重复字符都在 block 中，如"aaabbccccc"，代码行

if(i>0 && str.charAt(i) == str.charAt(i-1)) continue;

正是您所需要的。它不会错过任何排列，因为它只会跳过那些无论如何都会相同的排列。而且它不会重复任何排列，因为相同的字符在 block 中。

1. how can I prevent cases like a(1)ba(2)cd and a(2)ba(1)cd from happening when p=5. As for p=8 or 10, the trick I used will not be that efficient. so what I need to do?

我认为根本不需要担心像 "abacd" 这样的输入字符串。此字符串的排列组合与 "aabcd" 的排列组合完全相同，因此在开头对字符串进行排序是有意义的(这会将重复的字符收集到 block 中)，并调用 排列(“”，sortedString);。这样做你就可以使用你提到的技巧。

对于长字符串，它无论如何都会变慢，因为有很多排列，也因为该方法创建了很多字符串对象。这些因素比通过在比严格必要的稍大的范围内迭代并使用 continue 所造成的轻微低效率更为重要。