更快的字符串排列

问题描述

我有排列方法

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！组合，这需要很多时间.有没有可能使它更快?

But when I put string, which is 10 letters length into this method, it makes 10! combinations and it takes so much time. Is there any possibility how to make it faster?

编辑

我需要对10个字母进行排列，但是之后，我要在字典中搜索这些单词".例如，我有-CxRjAkiSvH，我需要单词CAR，CARS，CRASH等.是否有任何性能选项?

I need to make permutations from 10 letters, but after that, I search these "words" in dictionary. For example I have - CxRjAkiSvH and I need words CAR, CARS, CRASH etc. Is there any performance option?

推荐答案

现有的生成置换算法可能比您所使用的算法效率更高，因此您可以查看其中之一.过去，我使用过Johnson-Trotter算法，通过进行尽可能小的更改以获得每次下一个排列，该算法会略微加快速度.我不知道您必须使用哪种约束，但是如果您不必使用Java，最好不要这样做.它根本不会是最快的.尤其是在您的算法使用递归的情况下.正如其他人所建议的那样，如果您坚持使用此算法，则最好是远离递归方法并尝试使用循环.

There are existing algorithms for generating permutations which may be slightly more efficient than the one you're using, so you could take a look at one of those. I've used the Johnson-Trotter algorithm in the past, which gets a slight speed up by making the minimum change possible to get the next permutation each time. I don't know what kind of constraints you have to work within, but if you don't have to use Java it might be better not to. It simply won't be the fastest for this. Especially if your algorithm is using recursion. As someone else has suggested, if you're sticking with this algorithm you might be best served to move away from the recursive approach and try using a loop.

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