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.

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: