更快的字符串排列 [英] Faster string permutation

问题描述

我有排列方法

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?

推荐答案

现有的生成置换算法可能比您所使用的算法效率更高，因此您可以查看

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.

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