twitter/scalding — pull request #221 by krishnanraman (2012-11-07 02:47:37+00:00)
Title: Added combinations(n,k) to RichPipe

Added combinations(n,k) to RichPipe :

Given an int k, and an input of size n,
return a pipe with nCk combinations, with k columns per row

Computes nCk = n choose k, for large values of nCk

Use-case: Say you have 100 hashtags sitting in an array
You want a table with 5 hashtags per row, all possible combinations
But 100C5 is huge!!! Scala cannot handle it. But Scalding can!
If the hashtags are sitting in a string array, then
combinations[String]( hashtags, 5)
will do the needful.

Algorithm: Use k pipes, cross pipes two at a time, filter out non-monotonic entries

eg. 10C2 = 10 choose 2
Use 2 pipes.
Pipe1 = (1,2,3,...10)
Pipe2 = (2,3,4....10)
Cross Pipe1 with Pipe2 for 10*9 = 90 tuples
Filter out tuples that are non-monotonic
For (t1,t2) we want t1