librarylibs/Combinatorics/src/Combinatorics.xtl

Combinatorics: counting and listing -- factorials, binomials, combinations, permutations, subsets, Cartesian products. Import it with an alias of your choice: "cb:" u_se< "Combinatorics". Put libs/Combinatorics/src on XETAL_PATH ("just path"); the reference is libs/Combinatorics/docs. Names with l: are exported; those under h: are private to this file.

Lists come as matrices, one combination (or permutation, subset, pair) per row, in lexicographic order.

source

Counting

ˡf̲actorial : Int -> Int

function · line 13

f_actorial n: n!, item by item (0! is 1).

ˡf̲actorial ← { n → '{ '× r̲/ r̲ange ⍵ } e̲ach n }

ʰc̲h : Int -> Int -> Int

function (private) · line 16

C(n, k) for one k and n, exactly: C(n, j) = C(n, j - 1) * (n - j + 1) / j.

ʰc̲h ← { k n →
  (k < 0) ∨ k > n ? 0
  j ← k m̲in n − k
  j = 0 ? 1
  ((1 + n − j) × (j − 1) ʰc̲h n) d̲iv j
}

Used in: ʰc̲h, ˡc̲hoose

ˡc̲hoose : Int -> Int -> Int

function · line 24

k c_hoose n: how many ways to choose k things of n, item by item.

ˡc̲hoose ← { k n → k 'ʰc̲h e̲ach n }

Used in: tickets, ways

Listing

ˡc̲ombinations : Int -> Int -> Int

function · line 30

k c_ombinations n: every choice of k of 1..n, one per row, in lexicographic order (dfns cmat).

ˡc̲ombinations ← { k n →
  (k < 0) ∨ k > n ? (0 c̲at k) r̲eshape 0
  k = 0 ? 1 0 r̲eshape 0
  k = n ? (1 c̲at n) r̲eshape r̲ange n
  (1 c̲at₂ 1 + (k − 1) ˡc̲ombinations n − 1) c̲at 1 + k ˡc̲ombinations n − 1
}

Used in: ˡc̲ombinations, m

ʰf̲irstThen : (Num a, Truthy a) => a -> a -> a

function (private) · line 39

The rows of P (permutations of 1..n-1) with i put first and the others renumbered around it.

ʰf̲irstThen ← { i p → i c̲at₂ p + p ≥ i }

Used in: ˡp̲ermutations

ˡp̲ermutations : Int -> Int

function · line 43

p_ermutations n: every ordering of 1..n, one per row, in lexicographic order (dfns pmat).

ˡp̲ermutations ← { n →
  n ≤ 1 ? (1 c̲at n) r̲eshape 1
  p ← ˡp̲ermutations n − 1
  d̲isclose '{ e̲nclose (d̲isclose ⍺) c̲at d̲isclose ⍵ } r̲/ '{ i → i ʰf̲irstThen p } m̲ap r̲ange n
}

Used in: ˡp̲ermutations

ˡs̲ubsets : Int -> Int

function · line 51

s_ubsets n: every subset of 1..n as a mask, one per row: 2^n rows, counting in binary (the empty set first).

ˡs̲ubsets ← { n → o̲\ (n r̲eshape 2) e̲ncode o̲ffsets 2 ^ n }

Used in: ˡp̲owerset

ˡp̲owerset : a -> Box a

function · line 55

p_owerset v: every subset of the items of v, as a list (Box), in the order of s_ubsets.

ˡp̲owerset ← { v →
  m ← ˡs̲ubsets t̲ally v
  '{ i → (i s̲elect m) r̲eplicate v } m̲ap r̲ange t̲ally m
}

ˡp̲roduct : a -> a -> a

function · line 62

a p_roduct b: every pair of an item of a with one of b, one per row (a's items vary slowest).

ˡp̲roduct ← { a b →
  n ← (t̲ally a) × t̲ally b
  o̲\ (2 c̲at n) r̲eshape ((t̲ally b) r̲eplicate a) c̲at n r̲eshape b
}