6
\$\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\$
0

3 Answers 3

Reset to default
4
\$\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\$
5
  • \$\begingroup\$ I believe compiler optimization would convert String into StringBuilder. \$\endgroup\$
    – Vinay
    Commented Feb 12, 2014 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
    Commented Feb 12, 2014 at 6:40
  • \$\begingroup\$ @Vinay I doubt it too in this case. \$\endgroup\$
    – Vojta
    Commented Feb 15, 2014 at 14:23
  • \$\begingroup\$ Depends on the implementation of the compiler, Some wouldn't convert for Java \$\endgroup\$
    – Zuko
    Commented Apr 5, 2017 at 12:32
  • \$\begingroup\$ Can you suggest changes if repetition of characters is not allowed \$\endgroup\$
    – saran3h
    Commented Mar 15, 2019 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\$ Throwing wrong response. Try with 3 character \$\endgroup\$
    – Narender Gusain
    Commented Feb 10, 2021 at 11:42
-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\$
6
  • \$\begingroup\$ Thanks, this was also very helpful. I've never thought about it like that. Cheers. \$\endgroup\$
    – Phazor
    Commented Feb 12, 2014 at 7:26
  • \$\begingroup\$ That would cause it to create TWO new strings each time it runs: newCurr and curr + alphabet[i] \$\endgroup\$
    – TheCoffeeCup
    Commented Sep 28, 2014 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
    Commented Apr 16, 2015 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
    Commented Apr 16, 2015 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
    Commented Apr 17, 2015 at 3:41