Java搜索数组中所有可能的组合列表（算法）

Question

Java搜索数组中所有可能的组合列表（算法）

javastringperformancealgorithmdesign-patterns

3

我正在寻找一个数组中所有可能组合的列表。例如，考虑以下元素的数组：'A'，'B'，'C'，'D'。如果我选择一个最大字符串长度的数字，那么我想获得最大长度的所有数组的组合。例如：5 = 最大数字; 然后：A、AA、AAA、AAAA、AAAAA、AAAAB、AAAAC.......DDDDD。我编写了一段代码。在最大数字为10时，速度还可以。但对于超过15，它开始变得非常缓慢。有人有更好的想法来加快速度吗？这是我的代码:

public static void main(String[] args) {
    // TODO Auto-generated method stub
    HashSet<String> allResults = new HashSet<String>();
    // Create an alphabet to work with
    char[] alphabet = new char[] {'A','B','C','D'};
    // Find all possible combinations of this alphabet in the string size of 3
    StringExcersise.possibleStrings(15, alphabet,"", allResults);
    System.out.println(allResults.size());
}


    class StringExcersise {

public static void possibleStrings(int maxLength, char[] alphabet, String curr, HashSet<String> allResults) {
    // If the current string has reached it's maximum length
    if(curr.length() == maxLength) {
        allResults.add(curr);
        //System.out.println(curr);

    // Else add each letter from the alphabet to new strings and process these new strings again
    } else {
        for(int i = 0; i < alphabet.length; i++) {
            String oldCurr = curr;
            if(!allResults.contains(oldCurr))
                allResults.add(oldCurr);
            curr += alphabet[i];
            possibleStrings(maxLength,alphabet,curr,allResults);
            curr = oldCurr;
        }
    }
}
}

- clear.choi

任何算法都会变慢，因为您的解决方案空间的阶数为5的（n+1）次方，对于n=15而言，超过了一万亿。 - Bohemian

@Bohemian 真的吗？那太棒了.. 那我可能需要考虑如何减少可能的组合.. :) - clear.choi

顺便说一下，如果你需要高性能，可能在String上使用+=不是最好的选择，也许StringBuilder会更好。 - StepTNT

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joe · Accepted Answer

看一下这里的Heap's Algorithm链接

Java中的一个工作示例：

    private static void swap(int[] v, int i, int j) {
        int temp = v[i]; 
            v[i] = v[j];
            v[j] = temp;
    }

    public void permute(int[] v, int n) {
        if (n == 1) {
            System.out.println(Arrays.toString(v));
        } else {
            for (int i = 0; i < n; i++) {
                permute(v, n-1);
                if (n % 2 == 1) {
                    swap(v, 0, n-1);
                } else {
                    swap(v, i, n-1);
                }
            }
        }
    }