►Rebellion
▼8 Other Libraries
On this page:
permutation?
permutation
cyclic-permutation
empty-permutation
permutation-size
permutation-ref
permute
permuting
permutation-reverse
8.12
  top  contents    up   

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:
> (permute "abcd" (permutation 0 2 1 3) #:into into-string)

"acbd"

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

"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:
> (permute "abcdefghijklmnopqrstuvwxyz"
           (cyclic-permutation 5 17 25 8 0)
           #:into into-string)

"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

(permute seq perm [#:into reducer]) → any/c

  seq : (sequence/c any/c)
  perm : permutation?
  reducer : reducer? = (into-vector)
Rearranges the elements of seq according to perm, which must have the same size as seq has elements. The rearranged elements are collected into reducer which defaults to a reduction into a vector.

Examples:
> (permute '(a b c d e f) (permutation 4 1 5 3 0 2))

'#(e b f d a c)

> (permute "abcdef" (permutation 4 1 5 3 0 2) #:into into-string)

"ebfdac"

procedure

(permuting perm) → transducer?

  perm : permutation?
Constructs a transducer that rearranges the upstream elements according to perm and emits them downstream. Elements are emitted as soon as they’re available. The transduction consumes memory linear in the size of the permutation, but references to elements are not kept after they’ve been emitted downstream.

Example:
> (transduce "abcdef"
             (permuting (permutation 5 4 3 2 1 0))
             #:into into-string)

"fedcba"

procedure

(permutation-reverse perm) → permutation?

  perm : permutation?
Constructs the inverse permutation of perm, which permutes elements in exactly the opposite manner as perm. The inverse of a permutation effectively undoes that permutation.

Examples:
(define shift-right-once (permutation 1 2 3 4 5 0))

 

> (permute "abcdef" shift-right-once #:into into-string)

"bcdefa"

> (permute "abcdef" (permutation-reverse shift-right-once) #:into into-string)

"fabcde"

  top  contents    up