#lang scribble/doc

@(require scribble/manual
          (for-label scheme
                     "permutations.ss"))

@title{The Permutations PLaneT Package}

The permutations.plt PlaneT package provides utilities to generate and
manipulate permutations.  The permutations package is maintained by
@link["mailto:farr@mit.edu"]{Will M. Farr} and is released under the
@link["http://www.gnu.org/copyleft/gpl.html"]{GPL} (see the file
@filepath["GPL-3.0.txt"] in the main directory of the distribution for
more information).  Please direct any feature requests or bug reports
to Will at the above email address.

@section{Permutation Functions}

@defmodule[(planet wmfarr/permutations:1:3/permutations)]

@defproc[(permutation (obj any/c)) boolean?]{

@scheme[#f] unless @scheme[obj] is a permutation: a vector of n
elements which contains each of the numbers 0, 1, ..., n-1 exactly
once.  Note that this predicate is O(n) in the length of the vector
given!}


@defproc[(permutation-identity (n natural-number/c)) vector?]{

Returns @scheme[(vector 0 1 ... (sub1 n))]}


@defproc[(pvector-ref (p vector?) (v vector?) (i natural-number/c)) any]{

References the @scheme[(vector-ref p i)]-th element of the vector
@scheme[v].}


@defproc[(pvector-set! (p vector?) (v vector?) (i natural-number/c) (x any/c)) any]{

Sets the @scheme[(vector-ref p i)]-th element of the vector @scheme[v]
to @scheme[x].}


@defproc[(permutation-next! (v vector?)) (or/c vector? false/c)]{

Assuming @scheme[v] is a permutation, generates the next permutation
in lexigraphical order, and stores the result in @scheme[v].  Returns
the modified @scheme[v].  If @scheme[v] is the last permutation in a
lexical sequence of permutations, permutation-next! does not modify
@scheme[v] and returns @scheme[#f].  In this way, one can iterate over
permutations using code like

@schemeblock[
(let ((v (identity-permutation n)))
  (let loop ((p v))
    (when p
      (do-something-with-permutations p ...)
      (loop (permutation-next! p)))))]

without allocating new space for the permutation @scheme[p] on each
loop.}


@defproc[(permutation-next (v vector?)) (or/c vector? false/c)]{

Returns the permutation following @scheme[v] in lexigraphical order
without modifying @scheme[v].  If @scheme[v] is the last permutation
in a lexical sequence, returns @scheme[#f].}


@defproc[(permutation-signature (v vector?)) (one-of/c -1 1)]{

Returns either @scheme[1] or @scheme[-1] corresponding to whether
@scheme[v] is even or odd, respectively.  An odd permutation requires
an odd number of element interchanges to be turned into the identity
permutation; similarly for an even permutation.}


@subsection{Iterations Over Permutations}

The permutations package provides both an SRFI-42 generator and a
PLT-native generator for iterating over permutations in SRFI-42 loops
and @scheme[for]-like loops.

@defform*[((:permutations p-id n-expr) (:permutations p-id (index i-id) n-expr))]{

SRFI-42 generator for all @scheme[n]-element permutations.}


@defform[(in-permutations n-expr)]{

PLT-native sequence constructor for @scheme[n]-element permutations.}