5
\$\begingroup\$

I was asked in my textbook Lectures on Discrete Mathematics for Computer Science to construct a program that would take an alphabet ({a,b,c} or any combination of characters {1,4,s,a}) as well as a length value and calculate all possible combinations of this alphabet.

For example:

char[] alphabet = new char[] {'a','b'};
possibleStrings(3, alphabet,"");

This will output:

aaa
aab
aba
abb
baa
bab
bba
bbb

That is all combinations of the alphabet {a,b,c} with the string length set to 3.

The code I have written is functional, however I'd like to read what things I am doing wrong or could be doing better. The book didn't give an example program, so I only hope this is what it was looking for, but maybe there's a much better way to do it or way to improve how I'm doing it. Maybe this is fine, but I just need someone to look at it and tell me in that case.

public class Program {

    public static void main(String[] args) {

        // Create an alphabet to work with
        char[] alphabet = new char[] {'a','b'};
        // Find all possible combinations of this alphabet in the string size of 3
        StringExcersise.possibleStrings(3, alphabet,"");
    }

} class StringExcersise {

    public static void possibleStrings(int maxLength, char[] alphabet, String curr) {

        // If the current string has reached it's maximum length
        if(curr.length() == maxLength) {
            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;
                curr += alphabet[i];
                possibleStrings(maxLength,alphabet,curr);
                curr = oldCurr;
            }
        }
    }
}
\$\endgroup\$

migrated from stackoverflow.com Feb 12 '14 at 22:39

This question came from our site for professional and enthusiast programmers.

3
\$\begingroup\$

your code looks fine.

  • a slight performance improvement i'd do is pass a StringBuilder instead of a String - a String in java is immutable so every time you call curr += alphabet[i] youre actually allocating a new String object. instead you could append the character to a StringBuilder (and delete the last character when you leave) to save on the number of Objects created during the run
  • for(int i = 0; i < alphabet.length; i++) {} could be re-written as a more modern loop: for (char c : alphabet) {}, which would make for a more readable result
\$\endgroup\$
  • \$\begingroup\$ I believe compiler optimization would convert String into StringBuilder. \$\endgroup\$ – Vinay Feb 12 '14 at 6:39
  • 1
    \$\begingroup\$ @Vinay - if it was a straight-up long list of "+" ops youre right. im not so certain in this case. \$\endgroup\$ – radai Feb 12 '14 at 6:40
  • \$\begingroup\$ @Vinay I doubt it too in this case. \$\endgroup\$ – Vojta Feb 15 '14 at 14:23
  • \$\begingroup\$ Depends on the implementation of the compiler, Some wouldn't convert for Java \$\endgroup\$ – Olu Smith Apr 5 '17 at 12:32
  • \$\begingroup\$ Can you suggest changes if repetition of characters is not allowed \$\endgroup\$ – saran3h Mar 15 at 16:43
2
\$\begingroup\$

If the sequence is quite large then recursive methods can use up too much memory. This iterative approach works quite well.

private void generateCombinations(int arraySize, ArrayList<String> possibleValues)
{
    int carry;
    int[] indices = new int[arraySize];
    do
    {
        for(int index : indices)
            System.out.print(possibleValues.get(index) + " ");
        System.out.println("");

        carry = 1;
        for(int i = indices.length - 1; i >= 0; i--)
        {
            if(carry == 0)
                break;

            indices[i] += carry;
            carry = 0;

            if(indices[i] == possibleValues.size())
            {
                carry = 1;
                indices[i] = 0;
            }
        }
    }
    while(carry != 1); // Call this method iteratively until a carry is left over
}
\$\endgroup\$
-1
\$\begingroup\$

Instead of the oldCurr stuff, just create a newCurr each time. e.g.

String newCurr = curr + alphabet[i];
possibleStrings(maxLength, alphabet, newCurr);

Would be shorter and, at least to my eyes, is much clearer.

\$\endgroup\$
  • \$\begingroup\$ Thanks, this was also very helpful. I've never thought about it like that. Cheers. \$\endgroup\$ – Phazor Feb 12 '14 at 7:26
  • \$\begingroup\$ That would cause it to create TWO new strings each time it runs: newCurr and curr + alphabet[i] \$\endgroup\$ – TheCoffeeCup Sep 28 '14 at 17:47
  • \$\begingroup\$ @Manny Meng First, it only creates one new String, newCurr. Second, because Strings are immutable, you can't avoid this. In the OP's code curr += alphabet[i] also creates a new String. So your comment and downvote are incorrect. Finally even if one extra object were created, in this example nobody cares, it's only like 10 extra objects. \$\endgroup\$ – user949300 Apr 16 '15 at 16:51
  • \$\begingroup\$ Good first point, but for the second point, curr += alphabet[i] can easily be solved using a StringBuilder, as the accepted answer suggested. Also, 10 extra objects is a lot if you run this thousands or millions of times. For example, if the most optimized (i.e. no extra objects) method runs in, lets say, 10 milliseconds, and the other one takes 11 milliseconds, that's a 1,000 to 1,000,000 millisecond difference. \$\endgroup\$ – TheCoffeeCup Apr 16 '15 at 22:58
  • \$\begingroup\$ The StringBuilder will eventually be accessed viatoString(), creating an Object. Nowhere does OP suggest that this will be called thousands of times, let alone thousands of millions. \$\endgroup\$ – user949300 Apr 17 '15 at 3:41