Adding Results of Recursion to An ArrayList

Question

I'm trying to find all permutations of a word and add that to an Arraylist and return the array list. But, I believe my recursion is right but, there is a problem with adding the results to the ArrayList.This is what I have so far. The parameters I passed were "eat" and "" and what is returned is "tea" three times

public static ArrayList<String> permutations(String word, String beginning)
{
    int l = word.length();
    ArrayList<String> temp = new ArrayList<String>();

    if(l == 0)
        temp.add(beginning + word);
    else
    {
        char c = word.charAt(l-1);
        String blah = (beginning + c);
        word = word.substring(0, l-1);
        for(int i = 0; i < l; i++)
        {
            permutations(word, blah);
            temp.add(blah + word);
        }

    }
    return temp;
}

Where do you store the result of recursive calls? permutations(word, blah, temp); — issathink
– issathink, Commented Mar 1, 2015 at 23:15
Do you have another permutations method that takes 3 parameters? — jas
– jas, Commented Mar 1, 2015 at 23:16
permutations() has 2 parameters and you call it with 3. Is there another function ? — T.Gounelle
– T.Gounelle, Commented Mar 1, 2015 at 23:18
Also, i think this for-loop is not needed since the recursion-method is gonna go through the whole thing anyway... — Theodor Straube
– Theodor Straube, Commented Mar 1, 2015 at 23:19
@issathink whoops I just trying to pass the Arraylist as a parameter but, that seemed to work worse, so I changed it back. I just forgot to change all of it back but the result is still the same — Lola
– Lola, Commented Mar 1, 2015 at 23:22

jas · Accepted Answer · 2015-03-02 00:46:56Z

Probably I didn't have the right idea of your approach to find an easy fix and by the time I got things working I ended up with this. I hope it isn't too much of a departure and that it's still helpful. The output is:

[tea, tae, eta, eat, ate, aet]

import java.util.ArrayList;

public class Perm {
    public static void main(String[] args) {
        ArrayList<String> perms = new ArrayList<String>();
        permutations("tea", perms);
        System.out.println(perms);
    }

    public static ArrayList<String> permutations(String word, ArrayList<String> perms)
    {
        int l = word.length();

        // If the word has only a single character, there is only
        // one permutation -- itself. So we add it to the list and return
        if (l == 1) {
            perms.add(word);
            return perms;
        }

        // The word has more than one character.
        // For each character in the word, make it the "beginning"
        // and prepend it to all the permutations of the remaining
        // characters found by calling this method recursively

        for (int i=0; i<word.length(); ++i) {
            char beginning = word.charAt(i);

            // Create the remaining characters from everything before
            // and everything after (but not including) the beginning char
            String blah = word.substring(0,i)+word.substring(i+1);

            // Get all the permutations of the remaining characters
            // by calling recursively
            ArrayList<String> tempArray = new ArrayList<String>();
            permutations(blah, tempArray);

            // Prepend the beginning character to each permutation and
            // add to the list
            for (String s : tempArray) {
                perms.add(beginning + s);
            }
        }

        return perms;
    }
}

Collectives™ on Stack Overflow

Adding Results of Recursion to An ArrayList

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related