Results 1 to 12 of 12
  1. #1
    tfitz666 is offline Member
    Join Date
    Jul 2009
    Posts
    21
    Rep Power
    0

    Default 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 );
                }
            
            }
        }
    }
    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!

  2. #2
    senorbum is offline Member
    Join Date
    Aug 2009
    Posts
    76
    Rep Power
    0

    Default

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

  3. #3
    tfitz666 is offline Member
    Join Date
    Jul 2009
    Posts
    21
    Rep Power
    0

    Default

    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; 01-23-2010 at 06:19 PM.

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,776
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by tfitz666 View Post
    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:

    Java Code:
    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

  5. #5
    tfitz666 is offline Member
    Join Date
    Jul 2009
    Posts
    21
    Rep Power
    0

    Default

    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.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,776
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by tfitz666 View Post
    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

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,776
    Blog Entries
    7
    Rep Power
    21

    Default

    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<<hi-lo+1];
    		count(lo, hi, 0);
    		System.out.println(Arrays.toString(array));
    	}
    }
    kind regards,

    Jos

  8. #8
    tfitz666 is offline Member
    Join Date
    Jul 2009
    Posts
    21
    Rep Power
    0

    Default

    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.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.

  9. #9
    rdtindsm is offline Member
    Join Date
    Feb 2009
    Posts
    92
    Rep Power
    0

    Default 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
    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.
    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(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
    Last edited by rdtindsm; 01-24-2010 at 08:11 PM.

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,776
    Blog Entries
    7
    Rep Power
    21

    Default

    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

  11. #11
    rdtindsm is offline Member
    Join Date
    Feb 2009
    Posts
    92
    Rep Power
    0

    Default

    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!

  12. #12
    rdtindsm is offline Member
    Join Date
    Feb 2009
    Posts
    92
    Rep Power
    0

    Default

    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

  1. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 07:26 PM
  2. Recursion
    By Zosden in forum Algorithms
    Replies: 4
    Last Post: 05-05-2008, 06:49 AM
  3. help with recursion
    By Nari in forum New To Java
    Replies: 15
    Last Post: 04-24-2008, 10:13 AM
  4. Help With Recursion
    By andrew777 in forum New To Java
    Replies: 1
    Last Post: 03-29-2008, 01:51 PM
  5. recursion
    By ravian in forum New To Java
    Replies: 2
    Last Post: 12-03-2007, 06:15 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •