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')};


Please Wait...