Results 1 to 12 of 12
Thread: Recursion assignment problems
 01232010, 04:07 PM #1Member
 Join Date
 Jul 2009
 Posts
 21
 Rep Power
 0
Recursion assignment problems
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:
Java 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 ); } } } }
~/Desktop/cs2500/Lab6$ 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!
 01232010, 04:20 PM #2Member
 Join Date
 Aug 2009
 Posts
 76
 Rep Power
 0
I think one thing to notice is that abb is NOT a subset of abc. ab, ac, bc are all subsets.
 01232010, 05:15 PM #3Member
 Join Date
 Jul 2009
 Posts
 21
 Rep Power
 0
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.Last edited by tfitz666; 01232010 at 05:19 PM.
 01232010, 05:19 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
If a set has n elements then the number of all subsets is 2^n. Compare this to counting in binary:
Java Code:000  001 c 010 b 011 bc 100 a 101 ac 110 ab 111 abc
kind regards,
Jos
 01232010, 05:27 PM #5Member
 Join Date
 Jul 2009
 Posts
 21
 Rep Power
 0
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:
Subassignment 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 ndigit
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.
 01242010, 08:34 AM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
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
 01242010, 09:10 AM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
I just wanted to see if my reasoning made sense; it does; here's a spoiler; no comments because, well, it's a spoiler:
Java Code: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<<hilo+1]; count(lo, hi, 0); System.out.println(Arrays.toString(array)); } }
Jos
 01242010, 04:49 PM #8Member
 Join Date
 Jul 2009
 Posts
 21
 Rep Power
 0
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:
Java Code:char lo= args[0].charAt(0); char hi= args[args.length1].charAt(0);
Thanks again.
 01242010, 06:48 PM #9Member
 Join Date
 Feb 2009
 Posts
 92
 Rep Power
 0
solution from algorithm text
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.
Java Code: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 0471738840 Fourth Edition John Wiley & Sons, Inc. This book can be downloaded free of charge from http://www.ebooksspace.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 klength 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(k1,S,U) Add e back to U /*e is now unused */ Remove e from the end of S
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.
Java Code: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(progress1); 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
Last edited by rdtindsm; 01242010 at 07:11 PM.
 01242010, 07:37 PM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
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
 01242010, 08:28 PM #11Member
 Join Date
 Feb 2009
 Posts
 92
 Rep Power
 0
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!
 01242010, 09:18 PM #12Member
 Join Date
 Feb 2009
 Posts
 92
 Rep Power
 0
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.
Similar Threads

recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 06:26 PM 
Recursion
By Zosden in forum AlgorithmsReplies: 4Last Post: 05052008, 05:49 AM 
help with recursion
By Nari in forum New To JavaReplies: 15Last Post: 04242008, 09:13 AM 
Help With Recursion
By andrew777 in forum New To JavaReplies: 1Last Post: 03292008, 12:51 PM 
recursion
By ravian in forum New To JavaReplies: 2Last Post: 12032007, 05:15 PM
Bookmarks