java - 更快的字符串排列

Question

我有排列方法

public void permute(String str) {
    permute(str.toCharArray(), 0, str.length() - 1);
}

private void permute(char[] str, int low, int high) {
    if (low == high) {
        writeIntoSet(new String(str, 0, length));
    } else {
        for (int i = low; i <= high; i++) {
            char[] x = charArrayWithSwappedChars(str, low, i);
            permute(x, low + 1, high);
        }
    }
}

private char[] charArrayWithSwappedChars(char[] str, int a, int b) {
    char[] array = str.clone();
    char c = array[a];
    array[a] = array[b];
    array[b] = c;
    return array;
}

但是当我将 10 个字母长度的字符串放入此方法时，它变成了 10!组合，需要很多时间。有没有可能让它变得更快？

编辑

我需要对 10 个字母进行排列，但之后我会在字典中搜索这些“单词”。例如，我有 - CxRjAkiSvH，我需要单词 CAR、CARS、CRASH 等。有任何性能选项吗？

Answer 1

现有的用于生成排列的算法可能比您正在使用的算法稍微高效一些，因此您可以查看 one of those 。我过去使用过 Johnson-Trotter 算法，该算法通过每次尽可能进行最小的更改来获得下一个排列，从而稍微提高了速度。我不知道你必须在什么样的约束下工作，但如果你不必使用 Java，最好不要使用。它根本不会是最快的。特别是如果您的算法使用递归。正如其他人所建议的，如果您坚持使用此算法，您最好放弃递归方法并尝试使用循环。