Sets Without Replacement
December 18, 2019
[ Today’s exercise will be the last until next year. Expect the next exercise the week of January 6. In the meantime, enjoy the Christmas and New Year’s holidays with your families. ]
A set is an unordered collection of elements, and supports two operations: add an element, and delete an element. A set without replacement is a set where an element, once deleted from the set, cannot later be added back into the set.
Your task is to implement sets without replacement. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Quick perl class… keep everything in the single hash – key of each element is the value, the value of each element is true or false dependent on whether it has been deleted or not…. Use overload ‘””‘ to just dump the contents of the set…
package Set::NoReplace; sub new { bless {}, shift; } sub add { $_[0]{$_[1]} = 1 unless exists $_[0]{$_[1]}; } sub del { $_[0]{$_[1]} = 0 if exists $_[0]{$_[1]}; } use overload '""' => sub { return join ', ', sort grep { $_[0]{$_} } keys %{$_[0]}; }; my $x = Set::NoReplace->new; $x->add( 3 ); $x->add( 5 ); $x->add( 1 ); print $x, "\n"; $x->del( 3 ); print $x, "\n"; $x->add( 3 ); $x->add( 7 ); print $x, "\n";I’ve added it to code pad http://codepad.org/qY5FDiGn so you can see it in operation.
Here’s a solution in Python.
class Set(): def __init__(self): self.items = set() self.deleted = set() def add(self, item): if item not in self.deleted: self.items.add(item) def delete(self, item): self.deleted.add(item) self.items.remove(item) if __name__ == '__main__': s = Set() # Add 0-9 for x in range(10): s.add(x) print(s.items) # Delete 3 and 8 s.delete(3) s.delete(8) print(s.items) # Add 0-19 (3 and 8 will be ignored) for x in range(20): s.add(x) print(s.items)Output:
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} {0, 1, 2, 4, 5, 6, 7, 9} {0, 1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}