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}

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?

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

posted

0

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

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

posted

0

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

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

posted

0

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?