Recursion assignment problems

[tfitz666]

Hi,
I've been given an assignment to generate all the subsets of the argument passed in main(String[] args). The program must be recursive. I think I'm close, and as far as I can tell, it should work, but it doesn't:( Could you please help me iron out the kinks?
Here's my code:

public class SubGenTakeTwo{
    public static void main(String[] args){
        genSubs( args, 1, "", 0 );
    }
    
    public static void genSubs( String[] set, int n, String alreadyDone, int pos ){
              
        if( set.length < n ){
            System.out.println( "{ }" );
        } else {
            for( int index = pos; index < set.length; index++){
                if( n == 1 ){
                    alreadyDone = alreadyDone + set[index];
                } else {
                    alreadyDone = alreadyDone + set[index+1];
                }
                System.out.println( "{ " + alreadyDone + " }" );
                
                genSubs( set, n+1, alreadyDone, index );
            }
        
        }
    }
}

And here's the runtime error/incorrect results I'm getting in console:
~/Desktop/cs2500/Lab-6$ java SubGenTakeTwo a b c
{ a }
{ ab }
{ abb }
{ }
{ abbc }
{ }
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
at SubGenTakeTwo.genSubs(SubGenTakeTwo.java:20)
at SubGenTakeTwo.genSubs(SubGenTakeTwo.java:24)
at SubGenTakeTwo.genSubs(SubGenTakeTwo.java:24)
at SubGenTakeTwo.main(SubGenTakeTwo.java:8)

Any help greatly appreciated, thanks in advance!

[senorbum]

I think one thing to notice is that abb is NOT a subset of abc. ab, ac, bc are all subsets.

[tfitz666]

Yes, I realise that, I posted the incorrect results that I got in the hope that it'd give a clue as to what's going wrong.
P.S. I also realise that the set abc is not a proper subset of abc, but I still want it in the results.

[JosAH]

Yes, I realise that, I posted the incorrect results that I got in the hope that it'd give a clue as to what's going wrong.

If a set has n elements then the number of all subsets is 2^n. Compare this to counting in binary:

000 ---
001 --c
010 -b-
011 -bc
100 a--
101 a-c
110 ab-
111 abc

Look at the column on the right: it contains all the subsets of the set abc; does it ring a bell?

kind regards,

Jos

[tfitz666]

Thanks very much for the reply jos. I should have mentioned that we are not allowed use the method you outlined. Part 1 of this assignment was to print out binary numbers of length n recursively. Sorry for not mentioning that. Here's the exact wording of th question:

Sub-assignment 2: Subset Generation (10Marks)
In this part of the assignment you will generalise the previous assignment. Specifically, you are
asked to print all possible subsets of the argument args of your main method. For example, if
the arguments are given by {a,b,c} then the output of your program should be
{a,b,c}
{a,b}
{a,c}
{b,c}
{a}
{b}
{c}
{}
However, the order inwhich the lines are printed doesn’t matter. The order inwhich the members
of given set sets are printed also doesn’t matter.
You are not allowed to reuse the implementation of your previous assignment. For example,
if n is the number of arguments, then it should be possible to generate all possible n-digit
binary numbers and use them to print the relevant arguments: this is not allowed. Likewise,
you are not allowed to use existing Java collections classes. Finally, you are not supposed to
use temporary arrays to represent subsets. The sought solution requires a bit more innovation.
Again your core method should not require much code. It should be possible to implement
the core method in about 15 lines (comments excluded). Since this is not at all a trivial
assignment, it is expected that your comments clearly explain the idea behind your algorithm.

[JosAH]

You are not allowed to reuse the implementation of your previous assignment. For example,
if n is the number of arguments, then it should be possible to generate all possible n-digit
binary numbers and use them to print the relevant arguments: this is not allowed. Likewise,
you are not allowed to use existing Java collections classes. Finally, you are not supposed to
use temporary arrays to represent subsets. The sought solution requires a bit more innovation.
Again your core method should not require much code. It should be possible to implement
the core method in about 15 lines (comments excluded). Since this is not at all a trivial
assignment, it is expected that your comments clearly explain the idea behind your algorithm.

You are not allowed to do much ;-) Given the size n of the input set you can easily allocated a single String array of size 2^n. If you look at that little table in my previous reply again you can see that the entire set is composed of two copies of a smaller set and one of the copies has all of its elements prepended by a character 'a'.You can repeat that notion until you have a copy of the empty set (or String). Store all those Strings in that single array and you are done.

kind regards,

Jos

[JosAH]

I just wanted to see if my reasoning made sense; it does; here's a spoiler; no comments because, well, it's a spoiler:

import java.util.Arrays;

public class Counter {

	private static String[] array;
	
	private static int count(char lo, char hi, int offset) {
		
		if (lo > hi) {
			array[offset++]= "";
			return offset;
		}
		offset= count((char)(lo+1), hi, offset);
		for (int i= 0; i < offset; i++)
			array[i+offset]= lo+array[i];
		return 2*offset;
	}
	
	public static void main(String[] args){

		char lo= 'a';
		char hi= 'c';
		
		array= new String[1<<hi-lo+1];
		count(lo, hi, 0);
		System.out.println(Arrays.toString(array));
	}
}

kind regards,

Jos

[tfitz666]

Thanks for the replies. That's a clever solution, I don't think I'd have come up with something like that in a million years. In your solution the chars 'a' and 'c' are hardcoded, if you change those lines to:

char lo= args[0].charAt(0);
char hi= args[args.length-1].charAt(0);

you get a solution that works for all args passed. I won't hand up your solution but it will definitely help the next time I come across something like this.
Thanks again.

[rdtindsm]

I am working on a similar problem, (permutations) for my own edification. Newspaper has a daily puzzle to solve jumbled anagrams. I actually coded it in a procedural style (while loops) to try to understand the recursive solution, and never came back. That problem should generate the subsets along the way, but sets and subsets are not the same as permutations.

I am posting this because I hope the diagram will be helpful.

Simply for comparison, am including a procedural version. Note that I had to study the solution for some time to find the pattern for the ‘group length’ variable, and finally gave up trying to calculate a new value within a nested for loop. There is some code missing, but the solution works. I simply output the results to the console in eclipse and pasted the results into a word processor to use the spell checker. Found an open source spell checker and am working on a stand alone GUI app. Nearly through with it.

The following is From: 

   Data Structures and Algorithms in Java
Michael T. Goodrich
Department of Computer Science University of California, Irvine
Roberto Tamassia
Department of Computer Science Brown University
0-471-73884-0
Fourth Edition John Wiley & Sons, Inc.

This book can be downloaded free of charge from
http://www.ebooks-space.com/
________________________
Solving a combinatorial puzzle by enumerating and testing all possible configurations.

ALGORITHM PuzzleSolve(k,S,U)
   Input Integer K, sequence A, set U
   Output An enumeration of all k-length extensions to S using elements in U without repetitions

For each e in U do
   Remove e from U   /* e is now being used */
   Add e to the end of S
   if k=1 then
     Test whether S is a configuration that solves the puzzle
     if S solves the puzzle then
        return “Solution found:” S
     else PuzzleSolve(k-1,S,U)
     Add e back to U  /*e is now unused */
     Remove e from the end of S

In Figure 3.26, we show a recursion trace of a call to PuzzleSolve(3,S,U), where S is empty and U = {a,b,c}. During the execution, all the permutations of the three characters are generated and tested. Note that the initial call makes three recursive calls, each of which in turn makes two more. If we had executed PuzzleSolve(3,S, U) on a set U consisting of four elements, the initial call would have made four recursive calls, each of which would have a trace looking like the one in Figure 3.26.

Figure 3.26: Recursion trace for an execution of PuzzleSolve(3,S,U), where S is empty and U = {a, b, c}. This execution generates and tests all permutations of a, b, and c. We show the permutations generated directly below their respective boxes.

                         PuzzleSolve(3,(),(a,b,c))
                                 |
      -----------------------------------------------------
       |                                   |                                  |
PuzzleSolve(2,a,(bc))       PuzzleSolve(2,b(ac))         PuzzleSolve(2,c,(ab))
         |                                 |                                  |
------------------------   -----------------------   ------------------------
PS(1,ab,(c)) PS(1,ac,(b))  PS(1,ba,(c)) PS(1,bc,(a)  PS(1,ca,(b)) PS(1,cb,(a))
abc          acb           bac          bca          cab          cba


procedural solution
public void Permutator(String str){
   initPermutator(str);    // initialize storage and variables
                           // this included inserting e.g. the string “ab”
                           // as the initial solution from the string 
                           // “abcd...”.  

   int strLen = str.length();	  

   char inChar;
   int groupLen = 1;
   int progress = 3;
   
   
   for (int repCnt = 2; repCnt < strLen; repCnt++){
       ansNdx = 0;
       inChar = src.charAt(progress-1);
       while(ansNdx < aryLen){
    	   helper(groupLen, progress, inChar);
       } //while
// these recalculations can’t be done (??) as nested for loop.
       groupLen = groupLen * progress;
       progress++;      
   } //for
   
    revAndCopy(ans);    // take advantage of mirror image strings
} // end permutator 

//this function inserts the new character at each position
//over a portion of the array that can store 1/2 the permutations 
// of a string of length N.
   void helper(int groupLen, int progress, char nextChar){
	  
       for(int insertNdx = 0; insertNdx < progress; insertNdx++) {
          for(int i = 0; i < groupLen; i++){
                 ans[ansNdx].insert(insertNdx,nextChar);
                 ansNdx++;
          }
   } //
} // end helper

[JosAH]

The OP's problem was about enumerating combinations given a size n; as far as I can see your algorithm enumerates all permutations of n symbols? Care to elaborate what your algorithm has to solve?

kind regards,

Jos

[rdtindsm]

My first line stated that I was solving anagrams which is a permutation problem. I posted only as being relevant (similar) and indicated that that permutations and subsets were different problems. It was in no way intended to correct anyone else's code, only as a discussion of the similar problem. I thought that the purpose of Permutator(str) would be clear from the context.

Part of my intent in including my code was, which I should have stated and actulaly removed while from my reply while composing, is to show that recursive programs often code much cleaner than procedural resources. It is often helpful to code a recursive solution to help understand the problem, then convert to a procedural solution to save resources.

The newspaper problem presents four jumbled character sequences, two of 5 characters, two of six characters. The answers have one or more letters circled, and the enclosed letters are use to solve an anagram suggested by a cartoon. The puzzle is called JUMBLE. See Jumble, That Scrambled Word Game!

[rdtindsm]

A 5 letter anagram has 120 permutations, half of which will be a mirror image of another solution. For string "abcd", fill "ab" in 60 positions.
Then cab, acb, abc
+ d -> dcab, dacb, dabc, cdab, adcb, adbc, cadb, ....
The resulting series has a length of 12, and will be repeated 5 times.
adding d requires 60 insertions with one repetition.
Reverse each substring and copy into the other 60 positions.

Should have more expansive comments.