Create all combinations of length N from a given alphabet

Question

I have some (very limited) experience in Java 6 and decided to revisit the language. To do so I wrote a solution for the following challenge:

You are given a number N and a string S. Print all of the possible ways to write a string of length N from the characters in string S, comma delimited in alphabetical order.

The first argument will be the path to the input filename containing the test data. Each line in this file is a separate test case. Each line is in the format: N,S i.e. a positive integer, followed by a string (comma separated). E.g.

Print all of the possible ways to write a string of length N from the characters in string S comma delimited in alphabetical order, with no duplicates.

Input sample:

1,aa
2,ab
3,pop

Output sample:

a
aa,ab,ba,bb
ooo,oop,opo,opp,poo,pop,ppo,ppp

The code works but performance is pretty bad and it feels like this can be improved.

Please point out anything that is wrong with this. I'm especially interested to know if this could be written in an entirely different way using features of Java 8.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.File;
import java.io.IOException;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Set;
import java.util.HashSet;
import java.lang.String;
import java.lang.Integer;

public class Main
{
    public static List<String> create_combinations(List<Character> alphabet, int word_length)
    {
        List<Integer> index = new ArrayList<Integer>(word_length);
        for (int i = 0; i < word_length; ++i)
        {
            index.add(0);
        }
        List<String> results = new ArrayList<String>();

        for (;;)
        {
            StringBuilder word = new StringBuilder();
            for (int i = 0; i < index.size(); ++i)
            {
                word.append(alphabet.get(index.get(i)));
            }
            results.add(word.toString());

            for (int i = index.size() - 1; ; --i)
            {
                if (i < 0)
                {
                    return results;
                }

                index.set(i, index.get(i) + 1);

                if (index.get(i) == alphabet.size())
                {
                    index.set(i, 0);
                }
                else
                {
                    break;
                }
            }
        }
    }

    public static void main (String[] args) throws IOException
    {
        BufferedReader buffer = new BufferedReader(new FileReader(new File(args[0])));
        String line;
        while ((line = buffer.readLine()) != null)
        {
            int word_length = Integer.parseInt(line.substring(0, line.indexOf(',')));
            String letters = line.substring(line.indexOf(',') + 1);

            Set<Character> unique_letters = new HashSet<Character>();
            for (char c : letters.toCharArray())
            {
                unique_letters.add(c);
            }
            List<Character> alphabet = new ArrayList<Character>();
            alphabet.addAll(unique_letters);
            Collections.sort(alphabet);

            System.out.println(String.join(",", create_combinations(alphabet, word_length)));
        }
    }
}

Answer 1

Nitpicks

• You're using the "wrong" bracing style :). The vast majority of Java code-conventions enforces "egyptian" bracing style with the opening brace on the same line.

• The method name create_combinations is in "snake_case". The vast majority [...] "camelCase" variable naming. The method should be named createCombinations.

Approach

While you're using a pretty performant approach with StringBuffer, this can be improved a bit when working on a raw char[]. The vast majority of the costs here comes from creating the new Strings. That is something you won't be able to eliminate.

Furthermore you seem to have missed the "crucial point" of the challenge. What you're doing from a mathematical (or theoretical cs) point of view is counting. Your strings are fixed-width numbers.

Consider the following call:

createCombinations({'0', '1'}, 4);

the results are the following:

0000
0001
0010
0011
0100
0101
0110
0111
[...]
1111

You should see that this matches the binary numbers 0 to 15.

Now let's see what we can do with this information:

• Know how many results there will be. (namely \$a^c\$ with \$a\$ being the size of the alphabet and \$c\$ the length of the word)
• Count through the results.

This makes clear what our method signature will look like:

private String[] createCombinations(char[] orderedAlphabet, int wordLength) {

If you want to add some raw performance it would be a consideration to return a char[][] instead.

Enough talk about concepts: Here's how it looks:

public String[] createCombinations(char[] orderedAlphabet, int wordLength) {
    long resultCount = Math.pow(orderedAlphabet.length, wordLength);
    String[] result = new String[resultCount];
    char[] workingWord = new char[];
    for (int i = 0; i < workingWord.length; i++) {
        workingWord[i] = orderedAlphabet[0];
    }
    // initialization complete, algorithm starts:
    for (int i = 0; i < result.length; i++) {
        result[i] = new String(workingWord);
        int leastSignificantDigit = i % orderedAlphabet.length;
        workingWord[workingWord.length - 1] = orderedAlphabet[leastSignificantDig];
        // TODO propagate changes up the workingWord if the lsd is 0.  
        // [...]
    }
    return result;
}

Propagating the changes up the working word is left as a challenge for you.

Interestingly the observation about the "crucial point" of the challenge will allow you to formulate the challenge as a Stream. Do note that the stream will not have the state of a workingWord to ease computation (because streams must not have side-effects), which imposes a performance hit. Either way it's basically only a bit of hard thinking on how numbers work to get from IntStream.range(0, resultCount) to a Stream<String> containing all your results.