►SICM
▼2 General
On this page:
permutations
combinations
permute
sort-and-permute
subpermute
list-interchanges
permutation-interchanges
split-permutations
permutation-parity
exact-quotient
factorial
number-of-permutations
binomial-coefficient
number-of-combinations
    contents    up   

2.10 permute🔗

 (require sicm/general/permute) package: rktsicm

procedure

(permutations lst) → (listof list?)

  lst : list?

procedure

(combinations lst n) → (listof list?)

  lst : list?
  n : integer?
Generates all permutations or combinations of n elements from a list of elements.

procedure

(permute [permutation]) → list?

  permutation : (listof integer?) = [lst list?]
Generate the permutation of lst acccording to the permutation indexes permutation.

procedure

(sort-and-permute lst <? cont) → any/c

  lst : list?
  <? : less-than?
  cont : (-> list? list? (-> list? list?) (-> list? list?) any/c)
Based on a list of elements and a sorting function, generate the permutation that changes lst into the sorted list according to <?. Finally the cont function is called with the original lst sorted list, a permutation procedure that would convert the original lst into the sorted list, and the inverse permutation procedure that would permute a sorted list into the original lst.

procedure

(subpermute psteps lst) → list?

  psteps : (listof (cons integer? integer?))
  lst : list?
Permute part of a lst based on the steps of psteps, where each element of pstep is the cons of the new position with the old position.

Example:
> (subpermute '((1 . 4) (4 . 2) (2 . 3) (3 . 1)) '(a b c d e f))

'(a e d b c f)

procedure

(list-interchanges p-lst o-lst) → integer?

  p-lst : list?
  o-lst : list?

procedure

(permutation-interchanges p-lst) → integer?

  p-lst : (listof real?)
Count how many swaps between neighbouring elements are necessary to go from the permuted p-lst to the original o-lst. For permutation-interchanges the original list is defined as (sort p-lst <).

procedure

(split-permutations o-lst p-lsts cont) → any/c

  o-lst : list?
  p-lsts : (listof list?)
  cont : (-> (listof list?) (listof list?) any/c)
Split the list of permutated lists p-lsts according the fact if (even? (list-interchange p-lst o-lst)) and call cont on the even and odd lists.

procedure

(permutation-parity p-lst o-lst) → (or/c 1 0 -1)

  p-lst : list?
  o-lst : list?
Returns 1 if p-lst needs an even? number of interchanges to go to o-lst. -1 if it needs an odd? number of interchanges, and 0 if it is not a permutation of o-lst.

procedure

(exact-quotient n m) → integer?

  n : integer?
  m : integer?
Returns the quotient of n and m, but only if the remainder is 0. Otherwise raising an error.

procedure

(factorial n) → integer?

  n : integer?

procedure

(number-of-permutations n) → integer?

  n : integer?
Return the factorial of n: (* n (- n 1) (- n 2) ... 1)

procedure

(binomial-coefficient n k) → integer?

  n : integer?
  k : integer?

procedure

(number-of-combinations n k) → integer?

  n : integer?
  k : integer?
Return the binomial of n and k:
(/ (* n (- n 1) (- n 2) ... (- n k -1))
   (* k (- k 1) (- k 2) ... 1))

    contents    up