Search code examples
javarecursionsequences

Writing sequences program in Java using recursion


I've been tasked with a problem that finds all the subsequences for a string.

For example, if the string is "bat" the subsequences returns [,b, ba, at, bt, t]

Notice how it doesn't have all the permutations of the string since it has to go in order. The first string is an empty string and that's apparently requires by the instructions.

Another example is the string "brat". The expected output for that would be [, a, at, b, ba, bat, br, bra, brat, brt, bt, r, ra, rat, rt, t]

I've tried to write a program that would use recursion and give me the output but I've only gotten so far. I'm sure I understand recursion but I don't know how I would try to code this problem.

This is what I have so far:

import java.util.ArrayList;
public class Sequences {
   public static ArrayList<String> sequences(String s) {
      ArrayList<String> list = new ArrayList<String>();      
      return subsequences(s, list);
   }
   public static ArrayList<String> sequences(String s, ArrayList<String> list) {
       list.add("");
       if (s.length() == 0) 
           list.add(s);
       else {
           list.add(s);
           String temp = s.substring(0,1);
           String next = s.substring(1, s.length());
           list.add(temp);
           sequences(next);
       }
       return list;
   }
}

I also wrote a tester really quickly so I can test the problem since a tester wasn't provided to us:

  public class tester {
    public static void main(String[] args) {
        System.out.println(Sequences.sequences("at"));
    }
}

The output I'm getting is [, a] when I should have gotten [,a, at, t]

Any help would be welcome!


Solution

  • Your algorithm is wrong. One solution to the problem is this:

    In each step of recursion, put aside the first character and compute all subsequences of the rest. Then add all of the computed subsequences twice: once without the first character and another time with prepending the character.

    public class Sequences {
    
        public static ArrayList<String> sequences(String s) {
            ArrayList<String> list = new ArrayList<String>();
            if (s.length() == 0) {
                list.add("");
                return list;
            }
            String firstChar = s.substring(0, 1);
            String theRest = s.substring(1, s.length());
            ArrayList<String> siffixSequence = sequences(theRest);
            list.addAll(siffixSequence);
            for (String string : siffixSequence) {
                list.add(firstChar + string);
            }
            return list;
        }
    
        public static void main(String[] args) {
            System.out.println(Sequences.sequences("brat"));
            // prints [, t, a, at, r, rt, ra, rat, b, bt, ba, bat, br, brt, bra, brat]
        }
    
    }