Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Evaluating sets with recursion

John Lockheart
Ranch Hand
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
Posts: 24211
35
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?

John Lockheart
Ranch Hand
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
Posts: 24211
35
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
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
Posts: 24211
35
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
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
Posts: 24211
35
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
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?