*
The moose likes Java in General and the fly likes Evaluating sets with recursion Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Evaluating sets with recursion" Watch "Evaluating sets with recursion" New topic
Author

Evaluating sets with recursion

John Lockheart
Ranch Hand

Joined: Oct 13, 2006
Posts: 115
I have an array, where every element in the array is a circular linked list containing integers in each node. I need to write a subset method, which evaluates if one set is a subset of the other. My solution needs to be a recursive one. I got about as far as declaring two variable nodes to the beginning of both lists in setArray[0] and setArray[1]. And i'm kind of lost after that, using iteration would be no problem. Where should I even begin?

//Call in main program
setArray[0] = {1,2,3}
setArray[1] = {1,2,3,4,5,6}

setArray[0].subset(setArray[1]); //returns true
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

Given two sets A (containing A1, A2, A3.... An) and B, you could define A.subset(B) (A is a subset of B) as "A1 is a member of B, and also A'.subset(B)", where A' is (A2, A3... An). Along with the axiom that the empty set is a subset of every set, you've got a recursive solution right there. Make sense?


[Jess in Action][AskingGoodQuestions]
John Lockheart
Ranch Hand

Joined: Oct 13, 2006
Posts: 115
sort of, but i've tried implementing a non-iterative solution and still can't make it work.
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

Pseudocode version of the same thing:



Implementing size(), myOtherElements() and myFirstElement() are left as an exercise. Start with the most obvious implementation before you worry about efficiency, but do note that the need for efficient implementations of these operations should influence the choice of data structures to represent the set data.
John Lockheart
Ranch Hand

Joined: Oct 13, 2006
Posts: 115
I'm guessing the method contains would require a recursive solution itself as well? Something along the lines of just searching through the set for the given element?
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

It wouldn't require one, although you could write one; maybe "the argument is equal to my first element, or the rest of the set contains() the argument."
John Lockheart
Ranch Hand

Joined: Oct 13, 2006
Posts: 115
I haven't written them into the program yet, don't know if they compile. But I gave it a shot, does this look right?
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

Yes, this is all on the right track. otherElements() should return a new set, rather than mutating the current one -- i.e., it should not assign to this.top. And contains() needs an exit condition for the recursion -- i.e., what happens if the size is 0, or next() returns null?
John Lockheart
Ranch Hand

Joined: Oct 13, 2006
Posts: 115
Since it is a circular list, i was thinking of not having an exit condition in contains(), but limit the recursion call in subset().



as for otherElements, i can see creating a new set as an easy task using iteration, but if my solution was to only use recursion...seems like a pain. That's why I tried mutating. I guess I would have to create yet another method, to recursively create a new set then?
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Evaluating sets with recursion