Sets Without Replacement
December 18, 2019
Sets without replacement are easily implemented as two sets, one for the current elements and one for deleted elements. For simplicity, we implement sets as lists; you could use hash tables or binary trees if you prefer, or abstract sets from a previous exercise:
(define s (list)) ; set of current items (define t (list)) ; tombstones of deleted items
(define (add s x) ; add x to set s
(if (member x s)
(error 'add "can't add already existent element")
(if (member x t)
(error 'add "can't add previously existent element")
(begin (set! s (cons x s)) s))))
(define (del s x) ; remove x from set s
(if (not (member x s))
(error 'del "can't delete non-existent element")
(begin (set! s (remove x s))
(set! t (cons x t))
s)))
Here are some examples:
> (set! s (add s 1)) > (set! s (add s 3)) > (set! s (add s 5)) > (set! s (add s 3)) Exception in add: can't add already existent element > (set! s (del s 3)) > (set! s (add s 3)) Exception in add: can't add previously existent element > (set! s (del s 4)) Exception in del: can't delete non-existent element > s (5 1) > t (3)
You can run the program at https://ideone.com/0wwfjN.
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}