## 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)
(if (member x t)
(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))
> (set! s (del s 3))
> (set! s (add s 3))
> (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 { \$_{\$_} = 1 unless exists \$_{\$_}; }
sub del { \$_{\$_} = 0 if     exists \$_{\$_}; }
use overload '""' => sub { return join ', ', sort grep { \$_{\$_} } keys %{\$_}; };

my \$x = Set::NoReplace->new;
print \$x, "\n";
\$x->del( 3 );
print \$x, "\n";
print \$x, "\n";
```

2. Daniel said

Here’s a solution in Python.

```class Set():
def __init__(self):
self.items = set()
self.deleted = set()

if item not in self.deleted:

def delete(self, item):
self.items.remove(item)

if __name__ == '__main__':
s = Set()

for x in range(10):
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):
```{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}