HELP PERMUTATIONS                               David Young
                                                January 2003

LIB * PERMUTATIONS provides a procedure that generates all the
permutations of the elements of a structure. The results are produced by
a permutation repeater, which returns a new permutation each time it is
called, until all the possible permutations have been generated, at
which point it returns <termin>.

For example:

    vars i;
    for i from_repeater permutations({to boldly go}) do
        i =>
    endfor;

PERMUTATIONS(STRUCT) -> REP
PERMUTATIONS(STRUCT, CREATE_STRUCT) -> REP
        STRUCT may be any structure to which * EXPLODE may be applied
        (e.g. a list or vector). Permutations of its top-level elements
        will be generated.

        The result REP is a procedure of no arguments and one result:

                REP() -> NEWSTRUCT

        Each time it is called, REP returns a structure of the same type
        and with the same contents as the original argument, but with
        the elements possibly reordered. Each call of REP will produce a
        new permutation, though one of these will be the same as the
        original input. A single instantiation of REP will not produce
        the same permutation twice, except that repeated elements are
        not taken into account (so there will be 2 permutations of the
        list [a a]). After all possible permutations have been
        generated, REP returns <termin>; if called again after that a
        mishap will result.

        By default, the result NEWSTRUCT is a new structure created
        during the call to REP. If the optional second argument
        CREATE_STRUCT is included and is <false>, the permutations are
        stored in the original structure STRUCT, and this is then
        returned. This reduces garbage if different orderings do not
        need to be stored at the same time. CREATE_STRUCT, if given,
        must be a boolean and if <true> has the same effect as the
        default.

For details of the algorithm, see LIB * PERMUTATIONS. Lookup tables are
used to speed up the process, and this gives a speed/memory tradeoff
that may be controlled using the following variable.

PERMUTATION_TABLES -> INT
INT -> PERMUTATION_TABLES
        This active variable determines how many permutation tables are
        used. Tables are built for all sets of permutations up to length
        INT. The initial value may be found by inspecting the library or
        by printing this variable's value. For most purposes it is not
        necessary to change this variable.

        If PERMUTATION_TABLES is reduced, tables are released to the
        garbage collector, once any existing repeaters have terminated
        or been destroyed. If it is increased, new tables are created
        immediately, though existing repeaters will not use them. A
        value of 0 is acceptable, meaning use no lookup.

        In general, the more tables the faster the repeater will run,
        but the more memory will be used. The amount of memory is about
        (PERMUTATION_TABLES+1)! words, so a few tens of kilobytes
        for 6 tables, megabytes for 8 tables, and gigabytes for 11
        tables. Updating the active variable will also take time roughly
        proportional to the storage used.


--- $poplocal/local/help/permutations
--- Copyright University of Sussex 2003. All rights reserved.