Win a copy of Learn Spring Security (video course) this week in the Spring forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Evaluating sets with recursion

 
John Lockheart
Ranch Hand
Posts: 115
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic