How to find row `i` of `A= nchoosek(1:m,n)`

Question

I want to find A (i,:), where A= nchoosek(1:m,n), for given i, m, and n. This command of MATLAB is very time and memory consuming, specially for large m. So, I do not want to construct whole of A. I want to build just row i of A.

Although it seems that my question is duplicate of "Combinations from a given set without repetition", but they are different. It just gives acceptable results for A = nchoosek(1:m,2), and does not cover more than two columns.

score 2 · Accepted Answer · edited May 23 '17 at 11:58

I found a similar question on SO and implemented the proposed solution in MATLAB:

function [result] = kth_combination(k,l,r)

if r == 0
    result = [];
elseif size(l,2) == r
    result = l;
else
    i = nchoosek(size(l,2)-1,r-1);
    if k < i+1
        result = [l(1), kth_combination(k, l(2:end), r-1)];
    else
        result = kth_combination(k-i, l(2:end), r);
    end
end
end

There is another solution available on MATLAB File Exchange, which is not based on recursion: onecomb

In order to compare the 3 solutions, I created this benchmark function:

function [time_1,time_2, time_3] = compare_solutions(m,n,i,num_runs)
time_1 = 0;
time_2 = 0;
time_3 = 0;

for run=1:num_runs

    tic
    A=nchoosek(1:m,n);
    res_1 = A(i,:);
    time_1 = time_1 + toc;

    tic
    res_2 = kth_combination(i,1:m,n);
    time_2 = time_2 + toc;

    tic 
    res_3 = onecomb(m,n,i);
    time_3 = time_3 + toc;

    if (run==1) && (sum(res_1 ~= res_2) || sum(res_1 ~= res_3))
        error('solutions are NOT identical');
    end

end

time_1 = time_1/num_runs;
time_2 = time_2/num_runs;
time_3 = time_3/num_runs;

end

Sample run:

>>  [time_1,time_2, time_3]  = compare_solutions(20,10,10,10)

time_1 =

    1.9676

time_2 =

    6.8508e-04

time_3 = 

    7.1848e-05

Second and third solution are way faster than the nchoosek approach, the non-recursive one is even faster by factor 10 in comparison to the recursive one.

It is great. In addition, I am looking for a solution needed less memory. Although your proposed codes are faster, but they are still memory hungry. It is serious for large `m`. — Meher81, Apr 21 '15 at 04:37
May be 10^8. `n` is less than `10`. In this case, because of memory constraints, building whole of `A` is impossible. So, I am thinking for another way to find row `i` of `A`. — Meher81, Apr 21 '15 at 10:37
@Meher81: did you try the linked `onecomb` solution? it certainly is able to do what you want. — m.s., Apr 21 '15 at 12:05
Thanks a lot. I had not tested `onecomb`. It is exactly what I want! — Meher81, Apr 21 '15 at 14:21

How to find row `i` of `A= nchoosek(1:m,n)`

1 Answers1