CODEWITHSUNDEEP
javalistarraylist
Cyndi
Cyndi

Reputation: 59

Store data to list

Below is my requirements

Scramble the word into all possible permutations and store them in a list or array

What I have tried

public class Example {

    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        Example e = new Example();
        String changeCase = "ab";
        String result = changeCase.toLowerCase();
        list = e.permutation("", result);
        System.out.println("list size is "+list.size());


        for (String str : list) {
            System.out.println(str);
        }

    }

    private ArrayList<String> permutation(String prefix, String str) {
        ArrayList<String> l = new ArrayList<String>();

        int n = str.length();
        if (n == 0) {
            System.out.println(prefix);
            l.add(prefix);
        } else {
            for (int i = 0; i < n; i++) {
                permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
            }
        }
        return l;
    }
}

Output

ab
ba
list size is 0

I make sure all the value is added into list, but when I check the list size, it displays zero.

Upvotes: 2

Views: 85

Answers (5)

Joakim Danielson
Joakim Danielson

Reputation: 52098

Personally I would make the list a class member instead

public class Example {
  private List<String> result = new ArrayList<String>();

  public List<String> getResult() {
    return result;
  }

  private void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) {
        result.add(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
        }
    }
  }

  public static void main(String[] args) {
    Example e = new Example();
    String scramble = "abc";
    e.permutation("", scramble);

    for (String str : e.getResult()) {
        System.out.println(str);
    }
}

}

Upvotes: 0

vincrichaud
vincrichaud

Reputation: 2208

I've commented your code to point what is going on when you first call this method (prefix="" and str="ab") :

private ArrayList<String> permutation(String prefix, String str) {
    ArrayList<String> l = new ArrayList<String>(); //Create a new empty list

    int n = str.length();  //obtain the length of str ("ab") so n=2

    if (n == 0) {  //wrong cause n=2
        System.out.println(prefix);  //does not execute cause n=2
        l.add(prefix); //does not execute cause n=2

    } else {  //execute the else cause if condition is false
        for (int i = 0; i < n; i++) { //for each character in str
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));  //call a function and ignore the result
        }
    }  //end of else

    return l;  //return l, but since nothing was added to l, l is the empty list created at the beginning => l.size()=0
}

The problem in your recursion is that you re-create the list every time and ignore the result of sub-steps. You need to catch the result of sub-step and add it to your list.

private ArrayList<String> permutation(String prefix, String str) {
    ArrayList<String> l = new ArrayList<String>();

    int n = str.length();
    if (n == 0) {
        System.out.println(prefix);
        l.add(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            l.addAll(permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n))); //add the result of the sub-step to the list
        }
    }
    return l;
}

Upvotes: 0

Zefick
Zefick

Reputation: 2119

You create a new ArrayList for each recursive call of permutations instead of reusing the same list every time.

Possible solution:

public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<String>();
    Example e = new Example();
    e.permutation(list, "", result);
    ...
}

private void permutation(List<String> list, String prefix, String str) {
    int n = str.length();
    if (n == 0) {
        System.out.println(prefix);
        list.add(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            permutation(list, prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
        }
    }
}

Upvotes: 1

Pavneet_Singh
Pavneet_Singh

Reputation: 37414

you need to add the response of recursive calls(i.e. response list which contains the permutations) in your list as

l.addAll(permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n)));

Upvotes: 1

OneCricketeer
OneCricketeer

Reputation: 192013

You forgot to capture the recursion result

for (int i = 0; i < n; i++) {
    l.addAll(permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n))));
}

Upvotes: 0

Related Questions