►Rebellion
▼8 Other Libraries
On this page:
permutation?
permutation
cyclic-permutation
empty-permutation
permutation-size
permutation-ref
vector-permute
string-permute
7.7
  top  ← prev  up  next → 

8.5 Permutations

 (require rebellion/permutation) package: rebellion

A permutation is a rearrangement of a finite set, with elements of the set represented by natural numbers. More formally, a permutation of size n is a bijection from the set of natural numbers less than n to itself. Permutations are useful for efficiently expressing how collections are arranged, ordered, and sorted. Two permutations are equal? if they have the same size and rearrange elements in the same way.

procedure

(permutation? v) → boolean?

  v : any/c
A predicate for permutations.

syntax

(permutation position ...)

Constructs a permutation that moves the nth item in a collection to the nth position, with indices starting from zero. The resulting permutation’s size is equal to the number of positions given, and no duplicates are allowed. This form is equivalent to the standard one-line notation for permutations in mathematics.

Examples:
> (string-permute "abcd" (permutation 0 2 1 3))

"acbd"

> (string-permute "abcd" (permutation 3 2 1 0))

"dcba"

syntax

(cyclic-permutation position ...)

Constructs a permutation that moves the item at each position to the next position immediately following it. The item at the last position is moved to the first position. The resulting permutation’s size is equal to one plus the largest position given, and no duplicates are allowed. This form is equivalent to the standard cyclic notation for permutations in mathematics.

Example:
> (string-permute "abcdefghijklmnopqrstuvwxyz"
                  (cyclic-permutation 5 17 25 8 0))

"ibcdeaghzjklmnopqfstuvwxyr"

value

empty-permutation : permutation? = (permutation)

The empty permutation, which rearranges nothing. The size of the empty permutation is zero.

procedure

(permutation-size perm) → natural?

  perm : permutation?
Returns the size of perm.

Examples:
> (permutation-size (permutation 0 1 2 3 4 5))

6

> (permutation-size (cyclic-permutation 6 18 4 3 11))

19

procedure

(permutation-ref perm pos)

 → (and/c natural? (</c (permutation-size perm)))
  perm : permutation?
  pos : (and/c natural? (</c (permutation-size perm)))
Returns the resulting position of item pos when permuted by perm.

Examples:
> (define p (permutation 3 8 2 7 1 6 0 5 4))
> (permutation-ref p 0)

3

> (permutation-ref p 3)

7

> (permutation-ref p 8)

4

procedure

(vector-permute vec perm) → (and/c vector? immutable?)

  vec : (and/c vector? immutable?)
  perm : permutation?
Rearranges the elements of vec according to perm, which must have the same size as vec.

Example:
> (vector-permute (vector-immutable 'a 'b 'c 'd 'e 'f)
                  (permutation 4 1 5 3 0 2))

'#(e b f d a c)

procedure

(string-permute str perm) → (and/c string? immutable?)

  str : (and/c string? immutable?)
  perm : permutation?
Rearranges the characters of str according to perm, which must have the same size as str.

Example:
> (string-permute "abcdefg" (cyclic-permutation 4 5 6))

"abcdgef"

  top  ← prev  up  next →