## Friday, October 16, 2015

### 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:
```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)
```
Notes and caveats:
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: