Combinatorics.xtl

1⍝# Combinatorics: counting and listing -- factorials, binomials,
2⍝# combinations, permutations, subsets, Cartesian products.
3⍝# Import it with an alias of your choice: "cb:" u_se< "Combinatorics".
4⍝# Put libs/Combinatorics/src on XETAL_PATH ("just path"); the reference is libs/Combinatorics/docs.
5⍝# Names with l: are exported; those under h: are private to this file.
6⍝#
7⍝# Lists come as matrices, one combination (or permutation, subset,
8⍝# pair) per row, in lexicographic order.
9
10⍝## Counting
11
12⍝# f_actorial n: n!, item by item (0! is 1).
13ˡf̲actorial ← { n → '{ '× r̲/ r̲ange ⍵ } e̲ach n }
14
15⍝# C(n, k) for one k and n, exactly: C(n, j) = C(n, j - 1) * (n - j + 1) / j.
16ʰc̲h ← { k n →
17  (k < 0) ∨ k > n ? 0
18  j ← k m̲in n − k
19  j = 0 ? 1
20  ((1 + n − j) × (j − 1) ʰc̲h n) d̲iv j
21}
22
23⍝# k c_hoose n: how many ways to choose k things of n, item by item.
24ˡc̲hoose ← { k n → k 'ʰc̲h e̲ach n }
25
26⍝## Listing
27
28⍝# k c_ombinations n: every choice of k of 1..n, one per row, in
29⍝# lexicographic order (dfns cmat).
30ˡc̲ombinations ← { k n →
31  (k < 0) ∨ k > n ? (0 c̲at k) r̲eshape 0
32  k = 0 ? 1 0 r̲eshape 0
33  k = n ? (1 c̲at n) r̲eshape r̲ange n
34  (1 c̲at₂ 1 + (k − 1) ˡc̲ombinations n − 1) c̲at 1 + k ˡc̲ombinations n − 1
35}
36
37⍝# The rows of P (permutations of 1..n-1) with i put first and the
38⍝# others renumbered around it.
39ʰf̲irstThen ← { i p → i c̲at₂ p + p ≥ i }
40
41⍝# p_ermutations n: every ordering of 1..n, one per row, in
42⍝# lexicographic order (dfns pmat).
43ˡp̲ermutations ← { n →
44  n ≤ 1 ? (1 c̲at n) r̲eshape 1
45  p ← ˡp̲ermutations n − 1
46  d̲isclose '{ e̲nclose (d̲isclose ⍺) c̲at d̲isclose ⍵ } r̲/ '{ i → i ʰf̲irstThen p } m̲ap r̲ange n
47}
48
49⍝# s_ubsets n: every subset of 1..n as a mask, one per row: 2^n rows,
50⍝# counting in binary (the empty set first).
51ˡs̲ubsets ← { n → o̲\ (n r̲eshape 2) e̲ncode o̲ffsets 2 ^ n }
52
53⍝# p_owerset v: every subset of the items of v, as a list (Box), in
54⍝# the order of s_ubsets.
55ˡp̲owerset ← { v →
56  m ← ˡs̲ubsets t̲ally v
57  '{ i → (i s̲elect m) r̲eplicate v } m̲ap r̲ange t̲ally m
58}
59
60⍝# a p_roduct b: every pair of an item of a with one of b, one per row
61⍝# (a's items vary slowest).
62ˡp̲roduct ← { a b →
63  n ← (t̲ally a) × t̲ally b
64  o̲\ (2 c̲at n) r̲eshape ((t̲ally b) r̲eplicate a) c̲at n r̲eshape b
65}