CODEWITHSUNDEEP
javaarrayscombinatorics
S. Eisner
S. Eisner

Reputation: 11

Finding all possible combinations of all possible combinations of arrays

I have 13 arrays all containing unique characters. I want to be able to find and print out all possible combinations of all possible combinations of each array to a text file.

However, each array is of different length, ranging from 1 to 4 characters in length. Furthermore I don't want to change the order of the arrays, just the contents of the array.

My arrays are:

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'

The final array order should be: 0,1,2,3,4,5,6,7,8,9,10,11,12

As opposed to something like 0,2,4,6,8,7,5,3,1,9,10,11,12

Each combination of the characters in arrays 0 through 12 should be unique. If I calculated this correctly there should be slightly more than 100,000 different combinations.

I can't wrap my mind around how to solve this problem I have created for myself, and therefore any help is greatly appreciated.

Upvotes: 0

Views: 587

Answers (1)

Carsten
Carsten

Reputation: 2147

Recursion should help you to collect the 1,536 combinations:

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);
        }
    }
}

This produces the following output:

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

Just replace the System.out.println(leadPart + singleChar); with your file write command.

According to your comment, this method should be what you want:

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);
        }
    }
}

This produces 110592 combinations in the following format:

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

Upvotes: 3

Related Questions