java - 查找数组所有可能组合的所有可能组合

Question

我有 13 个数组，全部包含唯一字符。我希望能够找到每个数组的所有可能组合的所有可能组合并将其打印到文本文件中。

但是，每个数组的长度不同，长度范围为 1 到 4 个字符。此外，我不想更改数组的顺序，只想更改数组的内容。

我的数组是:

0    'Q'

1    'J'

2    'H','R'

3    'G','Y'

4    'D','L','C','U'

5    'E','T','A','O'

6    'W','F'

7    'I','N','S'

8    'Z'

9    'X'

10   'V','K'

11   'P','B'

12   'M'

最终的数组顺序应为:0,1,2,3,4,5,6,7,8,9,10,11,12

而不是像0,2,4,6,8,7,5,3,1,9,10,11,12

数组 0 到 12 中的每个字符组合都应该是唯一的。如果我计算正确的话，应该有略多于 100,000 种不同的组合。

我无法全神贯注于如何解决我为自己创建的这个问题，因此非常感谢任何帮助。

Answer 1

递归应该可以帮助您收集 1,536 种组合:

public static void main(String[] args) {
    List<char[]> characters = Arrays.asList(
            new char[][]{
                {'Q'},
                {'J'},
                {'H', 'R'},
                {'G', 'Y'},
                {'D', 'L', 'C', 'U'},
                {'E', 'T', 'A', 'O'},
                {'W', 'F'},
                {'I', 'N', 'S'},
                {'Z'},
                {'X'},
                {'V', 'K'},
                {'P', 'B'},
                {'M'}});
    printCombinationsToFile("", characters);
}

static void printCombinationsToFile(String leadPart, List<char[]> characters) {
    if (characters.size() == 1) {
        for (char singleChar : characters.get(0)) {
            // print your result string to your file
            System.out.println(leadPart + singleChar);
        }
    } else {
        List<char[]> remainingCharacters = characters.subList(1, characters.size());
        for (char singleChar : characters.get(0)) {
            // recursively collect all other combinations
            printCombinationsToFile(leadPart + singleChar, remainingCharacters);
        }
    }
}

<小时/>

这会产生以下输出:

QJHGDEWIZXVPM
QJHGDEWIZXVBM
QJHGDEWIZXKPM
QJHGDEWIZXKBM
QJHGDEWNZXVPM
QJHGDEWNZXVBM
QJHGDEWNZXKPM
QJHGDEWNZXKBM
QJHGDEWSZXVPM
QJHGDEWSZXVBM
QJHGDEWSZXKPM
QJHGDEWSZXKBM
...

只需将 System.out.println(leadPart + singleChar); 替换为文件写入命令即可。

<小时/>

根据您的评论，这个方法应该是您想要的:

static void printCombinationsToFile(String leadPart, List<char[]> characters) {
    if (characters.isEmpty()) {
        // print your result string to your file
        System.out.println(leadPart);
    } else {
        List<char[]> remainingCharacters = characters.subList(1, characters.size());
        char[] currentLevel = characters.get(0);
        for (int index = 0; index < currentLevel.length; index++) {
            List<char[]> remainingCombinations;
            if (currentLevel.length == 1) {
                remainingCombinations = remainingCharacters;
            } else {
                char[] currentLevelMinusOne = new char[currentLevel.length - 1];
                if (index > 0) {
                    System.arraycopy(currentLevel, 0, currentLevelMinusOne, 0, index);
                }
                if (index < currentLevelMinusOne.length) {
                    System.arraycopy(currentLevel, index + 1,
                            currentLevelMinusOne, index, currentLevelMinusOne.length - index);
                }
                remainingCombinations = new LinkedList<char[]>(remainingCharacters);
                remainingCombinations.add(0, currentLevelMinusOne);
            }
            // recursively collect all other combinations
            printCombinationsToFile(leadPart + currentLevel[index], remainingCombinations);
        }
    }
}

这会产生 110592 个以下格式的组合:

...
QJRHYGUCLDOAETFWSNIZXKVPBM
QJRHYGUCLDOAETFWSNIZXKVBPM
QJRHYGUCLDOATEWFINSZXVKPBM
QJRHYGUCLDOATEWFINSZXVKBPM
QJRHYGUCLDOATEWFINSZXKVPBM
QJRHYGUCLDOATEWFINSZXKVBPM
...