permutations of String Array in recursion

Question

String[] test = { "la", "li", "lo" };
language(3, test);

private String language(int n, String[] syllables) { // example of N = 3
    for (int i = 0; i < syllables.length; i++) {
        String w1 = syllables[i];
        for (int j = 0; j < syllables.length; j++) {
            String w2 = syllables[j];
            for (int x = 0; x < syllables.length; x++) {
                String w3 = syllables[x];
                System.out.println(w1 + w2 + w3);
            }
        }
    }
}

I'm trying to create a recursive method that can create any form of the String array. But I'm unable to achieve this

Variables

n = amount of syllables  
syllables = String Array of the base words

Output

lalala
lalali
lalalo
lalila
lalili
lalolo
lilala
lolala
lilili
lololo
......

You need to pick single character and then select other characters. Then call the same permutation() method on other character in the String. if size of string ==2 return the original as well as its reverse. concatenate all strings returned by negative calls. happy coding. — TheLostMind
– TheLostMind, Commented Sep 11, 2014 at 8:31
you are aware there will be n^n strings in the output (if all elements are unique)? — Mateusz Dymczyk
– Mateusz Dymczyk, Commented Sep 11, 2014 at 8:33
I think that strictly speaking, lalala is not a permutation of the 3 strings. A permutation needs to have all 3 strings in every string — shlomi33
– shlomi33, Commented Sep 11, 2014 at 8:39
@shlomi33 well that depends on the definition, some might call it a permutation with repetitions — Mateusz Dymczyk
– Mateusz Dymczyk, Commented Sep 11, 2014 at 8:41
Argh! Exception in thread "main" java.lang.StackOverflowError at java.lang.System.arraycopy(Native Method) — the_marcelo_r
– the_marcelo_r, Commented Sep 11, 2014 at 8:42

Florent Bayle · Accepted Answer · 2014-09-11 08:46:11Z

4

This will give you the result you are expecting:

String[] test = { "la", "li", "lo" };
language(3, test, "");

private static void language(final int n, final String[] syllables, final String currentWord) { // example of N = 3
    if (n == 0) {
        System.out.println(currentWord);
    } else {
        for (int i = 0; i < syllables.length; i++) {
            language(n - 1, syllables, currentWord + syllables[i]);
        }
    }
}

answered Sep 11, 2014 at 8:46

Florent Bayle

12k4 gold badges39 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user2803086 Over a year ago

Thanks, looks really understandable.

Mateusz Dymczyk Over a year ago

this also will print out duplicates for instance for {"la","la"}

user2803086 Over a year ago

for my purpose, it doesn't matter if the input contains a duplicate. Thanks for pointing out though

Florent Bayle Over a year ago

@MateuszDymczyk The question never said that this is something that should be avoided, but if you really want to, you can just replace the first call to language() by language(3, (new HashSet<String>(Arrays.asList(test))).toArray(new String[0]), "");

Mateusz Dymczyk Over a year ago

@FlorentBayle well I never said it's something really bad, just pointed it out as a potential problem/slowdown :-)

Nicktar · Accepted Answer · 2014-09-11 09:12:38Z

2

You'd need something along these lines:

private void recursiveMethod(int numberOfSyllablesToAdd, String[] syllables, String word) {
    for (int i = 0; i < syllables.length; i++) {
        String newWord = word + syllables[i];
        if (numberOfSyllablesToAdd >= 0) {
            recursiveMethod(numberOfSyllablesToAdd - 1, syllables, newWord);
       } else {
            System.out.println(newWord);
        }
    }
}

Note: This is really ineffective for multiple reasons (like not using a StringBuilder or StringBuffer to create the words)

edited Sep 11, 2014 at 9:12

answered Sep 11, 2014 at 8:38

Nicktar

5,5851 gold badge31 silver badges43 bronze badges

4 Comments

Mateusz Dymczyk Over a year ago

add that void there :-)

Florent Bayle Over a year ago

Another problem with your method: you have to pass 2 as the first parameter when first calling the method, instead of 3.

Mateusz Dymczyk Over a year ago

also it will print duplicates if the input array is not unique

user2803086 Over a year ago

Thanks for the efford, like Florent said, you have to pass a 2 instead of 3 to get a 3-syllable word.

Collectives™ on Stack Overflow

permutations of String Array in recursion

2 Answers 2

5 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related