sourcelibs/Random/src/Random.xtl
1⍝# Random: randomness -- shuffles, deals, choices, uniform and normal
2⍝# samples, weighted picks.
3⍝# Import it with an alias of your choice: "r:" u_se< "Random".
4⍝# Put libs/Random/src on XETAL_PATH ("just path"); the reference is libs/Random/docs.
5⍝# Names with l: are exported; those under h: are private to this file.
6⍝#
7⍝# Everything is built on the built-in r_oll!, so "xetal run --seed N"
8⍝# (or XETAL_SEED) makes a run repeatable. Every function has an effect
9⍝# and ends in !, as r_oll! does.
10
11big ← 1000000000 ⍝ the resolution of a draw
12
13⍝## Shuffling
14
15⍝# k random keys, 1..big.
16ʰk̲eys! ← { k → r̲oll! k r̲eshape big }
17
18⍝# s_huffle! v: the items of v in a random order (sorting random keys).
19ˡs̲huffle! ← { v → (g̲rade ʰk̲eys! t̲ally v) s̲elect v }
20
21⍝# k d_eal! n: k different numbers from 1..n, in random order (APL's deal).
22ˡd̲eal! ← { k n →
23 (k < 0) ∨ k > n ? @ p̲anic< "cannot deal {k} different numbers from 1 to {n}"
24 k t̲ake ˡs̲huffle! r̲ange n
25}
26
27⍝# c_hoice! v: one item of v, each as likely.
28ˡc̲hoice! ← { v →
29 0 = t̲ally v ? @ p̲anic< "there is nothing to choose from: the list is empty"
30 (r̲oll! t̲ally v) s̲elect v
31}
32
33⍝# k s_ample! v: k items of v, each drawn afresh (with replacement).
34ˡs̲ample! ← { k v →
35 (0 = t̲ally v) ∧ k > 0 ? @ p̲anic< "there is nothing to sample from: the list is empty"
36 (r̲oll! k r̲eshape t̲ally v) s̲elect v
37}
38
39⍝## Sampling distributions
40
41⍝# u_niform! n: n Floats, each as likely anywhere in [0, 1).
42ˡu̲niform! ← { n → (f̲loat (ʰk̲eys! n) − 1) ÷ f̲loat big }
43
44⍝# n_ormal! n: n Floats from the standard normal distribution (mean 0,
45⍝# standard deviation 1), by the Box-Muller transform.
46ˡn̲ormal! ← { n →
47 a ← 1.0 − ˡu̲niform! n ⍝ in (0, 1], so l_og is finite
48 b ← ˡu̲niform! n
49 ((-2.0 × l̲og a) ^ 0.5) × c̲os 2.0 × b × p̲i @
50}
51
52⍝# w w_eighted! k: k positions of w, each drawn with probability
53⍝# proportional to its weight (weights >= 0, not all 0).
54ˡw̲eighted! ← { w k →
55 c ← '+ s̲\ f̲loat w
56 u ← (f̲irst -1 t̲ake c) × ˡu̲niform! k
57 1 + '{ t̲ally w̲here c ≤ ⍵ } e̲ach u
58}
p̲anic< expands to
(⎕P̲ANIC ("cannot deal " c̲at (f̲ormat (k)) c̲at " different numbers from 1 to " c̲at (f̲ormat (n))))