如何查找`A = nchoosek（1：m，n）'的行'i`

Question

我想查找A (i,:)，其中A= nchoosek(1:m,n)，给定i,m和n。 MATLAB的这个命令非常耗时且耗费内存，特别适用于大型的m。所以，我不想构建整个A。我想要构建A的行i。

尽管看起来我的问题是“Combinations from a given set without repetition”的重复，但它们是不同的。它只为A = nchoosek(1:m,2)提供了可接受的结果，但不包括两个以上的列。

Answer 1

我发现了一个similar question on SO并实现在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 

有MATLAB的文件交换，提供另一种解决方案，它不是基于递归：onecomb

为了比较3解决方案，我创建了这个基准测试功能：

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 

样品运行：

>> [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 

第二个和第三个解决方案比nchoosek方法快，非递归的解决方案比递归的解决方案更快10倍。