A Combinatoric Combinator
I wrote this while I was playing around with using q on a hobby project, and I thought I’d share it in case anyone else might find it useful.
It takes a number
k
, a function f
, and a list or dictionary y
of count n
, and runs f
once for each of the k-combinations of y
. The result is returned as a dictionary with the function outputs as its values and its keys determined by the type of y
: if y
is a list, its keys are the subsets of y
that produced the outputs; if y
is a dictionary, its keys are the subsets of the keys of y
that index the subsets of y
that produced the outputs.
eachc:{
c:(where reverse 0b vs)each c@:where((first x)=sum 0b vs)each c:til"j"$2 xexp count y;
(last x)peach$[99h=type y;(key each y)!y:y{((key x)y)#x}/:c;y!y:y@/:c]}
Examples:
Notes and caveats:q)eachc[(3;sum)]til 5 0 1 2| 3 0 1 3| 4 0 2 3| 5 1 2 3| 6 0 1 4| 5 0 2 4| 6 1 2 4| 7 0 3 4| 7 1 3 4| 8 2 3 4| 9 q)eachc[(3;sum)]`a`b`c`d`e!til 5 a b c| 3 a b d| 4 a c d| 5 b c d| 6 a b e| 5 a c e| 6 b c e| 7 a d e| 7 b d e| 8 c d e| 9 q)
On little-endian machines (i.e. Sparc), the
reverse
will probably need to be removed.The size of the result set gets very big very quickly—an
n
of thirty is probably infeasible for most machines.I’ve written it to execute
f
on the combinations with peach
, rather than each
; this may or may not be appropriate, depending on the nature of any given f
and y
.Labels: contrib