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 it amounts to 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.