CODEWITHSUNDEEP
javaarraysstringalgorithmrecursion
Ary
Ary

Reputation: 47

Recursively generate string array of all combinations (of length k) of characters in a char array

For java practice, I'm trying to write a class that generates all combinations of letters in a character array and puts them in String array. The object should be built with a character array, and it should have a method that takes an int as input. The int will determine how long the combinations should be.

So, for example, input:

char[] charArray = { 'a', 'b' };
int k = 3;

Output:

[ "aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb" ]

The method should be recursive, each time it should call itself with k-1.

I've tried a simplified version, generating a String with all the permutations separated by an underscore, but I'm not getting the output I want.

public String generate(int k) {
    if (k == 0) return "_";
    String s = "";
    for (char c : charArray) {
        s = s+c+generate(k-1);
    }
    return s;
}

My output is:

"aaa_b_ba_b_baa_b_ba_b_"

Instead of:

"aaa_aab_aba_abb_baa_bab_bba_bbb"

Upvotes: 1

Views: 2174

Answers (2)

Andronicus
Andronicus

Reputation: 26076

Try something like this (uses java 8):

public String generate(String[] stringArray, String accumulator, int k) {
    if (k == 0) return accumulator;
    return Arrays.stream(stringArray).map(s -> generate(accumulator + s, k - 1)).collect(Collectors.joining("_"));
}

public String generate(String[] stringArray, int k) {
    returngenerate(stringArray, "", k);
}

I just needed to change the array of chars to array of Strings:

String[] stringArray = new String[]{ "a", "b" };

Then invoking the method generate(stringArray, 3) generates the result:

aaa_aab_aba_abb_baa_bab_bba_bbb

Upvotes: 1

Serhat Oz
Serhat Oz

Reputation: 798

You need one more parameter for your method which holds prevalues.

You can try below code segment for your purpose:

public static String generate(String prefix, int k) {
        String s = "";
        if (k == 0)
            return prefix + "_";

        for (char c : charArray) {
            String newPrefix = prefix + c;
            s = s + generate(newPrefix, k - 1); 
        }
        return s;
    }

This code will generate "aaa_aab_aba_abb_baa_bab_bba_bbb_" so you have to remove last underscore.

Upvotes: 1

Related Questions