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.

Pages: 1 2

2 Responses to “Sets Without Replacement”

  1. James Curtis-Smith said

    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.

  2. Daniel said

    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}
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: