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:
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/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!
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.
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
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.
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