java - 使用多线程生成字符串的所有组合

Question

我需要生成字符串的所有可能组合，使用多线程将工作平均分配给 N 个线程。所以字符串 cat 会输出:

c, a, t, ca, ct, ac, at, ta, tc, cat, cta, tac, tca, act, atc

每个线程都包含一个startIndex 和endIndex 并对字符串进行不同的处理。现在我可以生成一个字符串的所有排列，但我完全不知道我需要做什么来修改它以获得所有组合。任何帮助将不胜感激。

这是我现在拥有的:

public void run() {
    for(int i = startIndex; (i < endIndex); i++) {
        swap(word, 0, i); // Swap character to zero location.
        permuteAndCheck(word, 1); // Recursively check permutations
        swap(word, 0, i); // Undo swap
    }
}

private void permuteAndCheck(char[] word, int start) {
    if (start < word.length) {
        // Not yet at the deepest recursion level to compare permutations.
        for(int i = start; (i < word.length); i++) {
            swap(word, start, i);
            permuteAndCheck(word, start + 1);
            swap(word, start, i); // Restore entry back from previous swap
        }
        return;
    }

    System.out.print(word + ", ");
}

private static final void swap(char[] word, int index1, int index2) {
    char temp  = word[index1];
    word[index1] = word[index2];
    word[index2] = temp;
}

Answer 1

如果您正在寻找所有组合(即字符的幂集)，那么您已经知道有 2^k 种可能性，k 是字符数。

然后第一个线程处理第 1 到第 (2^k)/N 个组合，第二个线程处理第 1+ (2^k)/N 到 2*(2^k)/N 个组合，等等

要获得第 j 个字符串，您可以查看 j 的二进制表示，并获取对应数字为“1”的字符。即“cat”的第 5(binary:101) 组合是 c_t。