#items #space #algorithm #knuth #choosing

app pick

Simple program implementing Knuth's algorithm for choosing n from M items in O(n) space

2 releases

0.1.1 Jul 27, 2020
0.1.0 Jul 27, 2020

#144 in #items

MIT license

5KB
85 lines

pick

A short and simple program implementing Knuth's algorithm for picking n items from a list of M items. The size of M may not be known until the list terminates, and it still only requires O(n) space.

Dependencies

~1.8–2.5MB
~46K SLoC