Finding unordered sequences of Java String Array in recursion

Question

I have to create an algorithm which shows all the available unordered sequences of fixed lengths using a String array. The method needs to be recursive and may only take one integer. It also needs to return a String array.

Let's say I have "ab" and "ba". The following unordered sequences of fixed lenghts should be found when I'm giving the int 2 with the method:

abab
abba
baba
baab

I've been working for hours now and I have the feeling that I'm working way too hard for this simple thing. I have had different kinds of code and I had it almost working (abba was shown twice instead of another sequence) but I forgot to return it in an array so that caused problems... The code I have looks like this, but is unfinished and doesn't work:

static String[] syllables = {"ab", "ba"};
static String[] syllableWord;

public static void main(String[] args) {
    int amountOfSillables = 2;
    syllableWord = String[(int)Math.pow(amountOfSillables, amountOfSillables)];
    String[] syllableWords = findSequences(amountOfSillables); // I may only use one parameter,
                                     // which is 2 but should work with any number

    for (int i = 0; i < syllableWords.length; i++) {
        System.out.println(syllableWords[i]);
    }
}

public static String[] findSequences(int n) {
    if (n == 0) {
        return syllableWord;
    }
    else {
        for (int i = 0; i < syllables.length; i++) {
            syllableWord += syllables[i]; // Doesn't work because syllableWord is an array.
                                          // When it's a String this would kinda work, but it 
                                          // needs to be an array.
            findSequences(n - 1);
            syllableWord = syllableWord.substring(2); // Also doesn't work when it's an array.
        }
    }
}

Can somebody help me out? This is driving me crazy...

syllableWord can't be acces from perm method. Because syllableWord is a local variable defined in main method — Thusitha Thilina Dayaratne, Sep 11 '14 at 14:09
Why are you requesting to have only one parameter (an integer) in your recursive call? — R2B2, Sep 11 '14 at 14:10
You cant add items to array using +=. There are many compilations errors in this code — Thusitha Thilina Dayaratne, Sep 11 '14 at 14:11
Isn't this what you are looking for? http://stackoverflow.com/questions/20906214/permutation-algorithm-for-array-of-integers-in-java — Enermis, Sep 11 '14 at 14:13
And "abab" is not a permutation of "ab" and "ba". You are trying to find unordered sequences of fixed length, not permutations. — R2B2, Sep 11 '14 at 14:17
@ThusithaThilinaDayaratne, Sorry, I'm using two different kinds of syllableWord. One in the method (which isn't being defined here) and one in the main method. — Tom, Sep 11 '14 at 14:38
@R2B2 It isn't? Oops, well, I'm sorry. I'm trying to find unordered sequences of fixed lengths then. Thank you. I'll edit my question. — Tom, Sep 11 '14 at 14:39

score 1 · Accepted Answer · answered Sep 11 '14 at 14:19

1

Something like this ? (using ArrayList is smarter than Array as you did not need to manage array size, depends on your needs)

public static List<String> perm(int n) {
    List<String> result = new ArrayList<String>();
    if (n == 1) {
        return Arrays.asList(syllables);
    }
    for (String s : syllables) {
        for (String prefix : perm(n - 1)) {
            result.add(s + prefix);
        }
    }
    return result;
}

answered Sep 11 '14 at 14:19

yunandtidus

3,847
3
29
42

This is actually what I was looking for, but I can't use an ArrayList (though I know it is way more convenient because it hasn't got a fixed size..) – Tom Sep 11 '14 at 14:56
I meant as a return value. I can however use it within the method and convert it to a regular array just before returning it. Thank you! I've modified your code so that the return value is a String array. String [] stockArr = result.toArray(new String[result.size()]); return stockArr; and it works. Thanks all for thinking with me! – Tom Sep 11 '14 at 15:02

score 0 · Answer 2 · answered Sep 11 '14 at 14:28

I am not exactly using your template, and I use more than an integer in my recursive calls.

I only use one array and there is very little post-computation after the recursive calls, so it should be quite efficient.

public static String[] perm(String[] data) {
    int n = (int) Math.pow(data.length, data.length);
    String[] result = new String[n];
    algo(data, result, 0, n, new StringBuilder());
    return result;
}

private static void algo(String[] data, String[] result, int offset, int width, StringBuilder acc) {
    if(width == 1) {
        result[offset] = acc.toString();
        return;
    }
    width /= data.length;
    for(int i=0; i<data.length; i++) {
        acc.append(data[i]);
        algo(data, result, offset+i*width, width, acc);
        int s = acc.length();
        acc.delete(s-data[i].length(), s);
    }
}

score 0 · Answer 3 · answered Sep 11 '14 at 14:30

Assuming you only want to display the value, the following should work:

public static void main(String args[])
{

    final String[] syllables = new String[] { "ab", "ba" };
    final List<String> path = new ArrayList<String>();
    recursiveDisplay(syllables, path, 0);

}

private static void recursiveDisplay(final String[] syllables, List<String> path, final int index)
{

    if (index < syllables.length - 1)
        for (int i = 0; i < syllables.length; i++)
        {
            path.add(syllables[i]);//add current token
            recursiveDisplay(syllables, path, index + 1);//process updated path
            path.remove(path.size() - 1);//remove processed token
        }
    else
    {
        // we have reached the end of the tree
        // let's display all possible combination of this path

        StringBuilder buidler = new StringBuilder();
        for (final String token : path)
            buidler.append(token);

        for (final String token : syllables)
            System.out.println(buidler + token);
    }

}

Finding unordered sequences of Java String Array in recursion

3 Answers3