To compare n files, the total comparison count is: $$ {{n}\choose{k}} = C^k_n = \dfrac{n!}{k! ( n - k )!} $$
with k = 2. Input space is composed by all pairs of files to compare. I want to split input space by the number of processor available to parallelize comparison. Dividing the input space doesn't divide the comparison's count equally.
If file's count is 100, the comparison's count is 4 950, with 4 processors: processors 1, 2 and 3 should do 1 237 comparisons and processor 4 should do 1 239 comparisons.
Dividing 100 per 4 gives this comparison's count for each processor:
- p1: files 1.. 25, first compared to the next 99 files, second to 98 -> 2 175 comparisons
- p2: files 26.. 50 -> 1 550 comparisons
- p3: files 50.. 75 -> 925 comparisons
- p4: files 76..100 -> 300 comparisons
The correct ranges, empirically determined, are [0..13[ (1295 comparisons), [13..29[ (1240 comparisons), [29..50[ (1239 comparisons) and [50..100[ (1 176 comparisons)
I need the reverse function of $ C^k_n $ to determine n from the comparisons count.
Your situation actually seems to allow to think less complicated and solve the problem in a somewhat easy way.
So, your problem is that you want to compare $n$ files, leading to $\binom{n}{2} = \frac{n(n-1)}{2}$ comparisons in total. You want to distribute the file comparisons equally on your $p$ processors.
Let's define a function (for $1\leq a\leq b \leq n$) $$ f(a,b) = \sum_{i=a}^b (n-i) = (b-a+1)n - \sum_{i=1}^{b-a+1} (i+a-1) \\ = (b-a+1)(n-a+1) - \frac{1}{2} (b-a+1)(b-a+2). $$ This function $f$ counts how many comparisons one processor would have to make if it had to do the comparisons for file number $a$ to file number $b$.
So, since we would want to split the comparisons equally we want that each processor has to do about $n(n-1)/(2p)$ comparisons. Assuming that processor one starts at file number one this leads to the following problem for the first processor: $$ \frac{n(n-1)}{2p} \approx f(1,c) = cn-\frac{c(c+1)}{2} $$ where $c$ is unknown. If we treat the $\approx$ as $=$ we get by simply moving the terms and multiplying by factor two the equation $$ c^2 + (1-2n)c + \frac{n(n-1)}{p} = 0. $$ This is a polynomial of degree two in $c$, which can be solved easily using the known solution formula. This leads to $$ c_{\alpha,\beta} = \frac{1}{2} \left( (2n-1) \pm \sqrt{ (1-2n)^2 - 4 \frac{n(n-1)}{p}} \right). $$ Given your example with $n=100$ and $p = 4$ you'd get $c_\alpha \approx 13.33$ and $c_\beta \approx 185.67$ (where the latter solution makes no sense, obviously). So, by rounding that result you'd decide to give the first $c_1:=13$ files to processor one, which coincides with your observation.
If you want to determine how many files you have to give to the next processor you'd now try to solve the problem $$ \frac{n(n-1)}{2p} \approx f(c_1+1, c) $$ which again leads to a quadratic problem and $c_1$ is the value you determined in the previous step.
So in total you'd have to solve $(p-1)$ quadratic equations, which should be a doable effort for your program. I'd suggest to write a function that solves the equation $$ \frac{n(n-1)}{2p} \approx f(a, c) $$ for $c$ when $n$, $p$ and $a$ are given function parameters.
Edit: As little remark, you would want to ensure something like $c_{i+1} > c_{i}$ for your processors. Because if you happen to get as result of some rounding that one of your processors would actually end up with no file at all, you would get stuck in a loop and then the last processor would end up with too many files. This actually should never ever happen since you probably have way more comparisons than processors... but I thought it was still worth mentioning.