:

## Building a Set

Maple

I recently discovered a minor variation on the technique of building a set using a table. The purpose for using a table rather than inserting new items directly into a set is that, in a loop, the latter technique is O(n) rather than O(n).  The way I would normally do this is to assign a counter and an empty table, and then, in a loop, compute the new element, increment the counter, and insert the element into the table at the counter index.  For example,

```T := table();
cnt := 0:
while not finished() do
x := compute();
if acceptable(x) then
cnt := cnt+1;
T[cnt] := x;
end if;
end do;
# convert T to a set:
S := {seq(T[i], i = 1..cnt)};
```

Because we are creating a set---so order is not important and terms occur once---a minor optimization is possible.  Rather than saving the value as an entry in the table, save it as an index, with a NULL entry. This eliminates the need for a counter.

```T := table();
while not finished() do
x := compute();
if acceptable(x) then
T[x] := NULL;
end if;
end do;
S := {indices(T,'nolist')};
```

Note that with the previous method we could have used

S := {entries(T,'nolist')};

﻿