1 Permutation Functions
1.1 Iterations Over Permutations
: permutations

The Permutations PLaneT Package

The permutations.plt PlaneT package provides utilities to generate and manipulate permutations. The permutations package is maintained by Will M. Farr and is released under the GPL (see the file "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.

1 Permutation Functions

 (require (planet wmfarr/permutations:1:3/permutations))

(permutation obj)  boolean?

  obj : any/c

#f unless 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!

(permutation-identity n)  vector?

  n : natural-number/c

Returns (vector 0 1 ... (sub1 n))

(pvector-ref p v i)  any

  p : vector?

  v : vector?

  i : natural-number/c

References the (vector-ref p i)-th element of the vector v.

(pvector-set! p v i x)  any

  p : vector?

  v : vector?

  i : natural-number/c

  x : any/c

Sets the (vector-ref p i)-th element of the vector v to x.

(permutation-next! v)  (or/c vector? false/c)

  v : vector?

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

  (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 p on each loop.

(permutation-next v)  (or/c vector? false/c)

  v : vector?

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

(permutation-signature v)  (one-of/c -1 1)

  v : vector?

Returns either 1 or -1 corresponding to whether 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.

1.1 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 for-like loops.

(:permutations p-id n-expr)

(:permutations p-id (index i-id) n-expr)

SRFI-42 generator for all n-element permutations.

(in-permutations n-expr)

PLT-native sequence constructor for n-element permutations.