在重新排序的大矩阵中查找重新排序的向量的索引

Question

假设我有一个重新排列的矩阵A，它是通过在MATLAB中使用A = nchoosek(1:100, 6)得到的。因此，A通过选择从1 6位〜100

A意味着所有组合被重新排序，并且A昏暗是非常大的（1E9 * 6），所以A是这样的：

1  2  3  4  5  6 
1  2  3  4  5  7 
1  2  3  4  5  8 
.  .  .  .  .  . 
.  .  .  .  .  . 
94 96 97 98 99 100 
95 96 97 98 99 100 

然后，我有另一个重新排列的向量B，它是A的成员。如B=[5 10 11 40 51 67];

那么，如何使用最快的方式找到B的索引，这意味着利用排序信息？

Answer 1

您应该注意如何生成A的行。我怀疑这不是在文档中指定的，所以你可能不应该太依赖它。我的意思是这是技术上没有记录的行为，它可以随任何版本改变。

但请注意，每个元素从结尾索引开始循环，并且每个组合都进行排序。这意味着你需要从头开始，在

B = [5 10 11 40 51 67]; 

第一指数为5，这意味着所有的开始4的元素都被一一列举。这些有多少？

nchoosek(100-1,6-1)+nchoosek(100-2,6-1)+nchoosek(100-3,6-1)+nchoosek(100-4,6-1) 
% [1 . . . . .]  [2 . . . . .]  [3 . . . . .]  [4 . . . . .] 
% ^2:100   ^3:100   ^4:100   ^5:100 

，因为我们有99个号码从如果第一元素是1，98选5至从如果第一数目是2选择5等

接下来是元件[5 6 7 8 9 10]通过[5 9 97 98 99 100]。同样，这些都充满组合，如果第二个元素是固定的：

nchoosek(100-6,6-2)+nchoosek(100-7,6-2)+nchoosek(100-8,6-2)+nchoosek(100-9,6-2) 
% [5 6 . . . .]  [5 7 . . . .]  [5 8 . . . .]  [5 9 . . . .] 
% ^7:100   ^8:100   ^9:100   ^10:100 

依此类推，直到建立所有的[5 10 11 40 50 .]，其中包含nchoosek(100-50,6-5)的最后一项。然后剩下的就是计算从[5 10 11 40 51 52]到[5 10 11 40 51 67]的元素，即67-52+1。

所以，正式的，如果你的索引向量B有n个元素，每一个为k=1:n称为b_k：

sum_{k=1:n} sum_{b=b_{k-1}+1:b_{k}-1} nchoosek(100-b,n-k) 

如果我们定义b_0成为第一个指数为零，这将正常工作，并注意nchoosek(m,0)==1 。

所以这里是一个应该工作的直接函数。这不是在同类最佳的，但可以肯定的节拍互相检查1E9载体：

function ind = find_chooseind(N,B) 
% N is the N in 1:N in nchoosek(1:N,K) 
% length(B) == K 

% define auxiliary B with a zero prepended to avoid out-of-bounds errors 
Blen = length(B); 
B = [0; B(:)]; 

ind = 0; 
for k=2:Blen+1 % shifted for that first zero 
    for b=B(k-1)+1:B(k)-1 
     ind = ind + nchoosek(N-b,Blen-(k-1)); % compensate for k shift 
    end 
end 

% testing reveals an off-by-one error, not to worry 
ind = ind+1; 

我测试了上面的代码以较小的例如：

>> N = 20; K = 4; 
>> A20_4 = nchoosek(1:N,K); 
>> t = A20_4(randi(nchoosek(N,K)),:); 
>> ind = find_chooseind(N,t); 
>> A20_4(ind,:) 

ans = 

    7  8  9 14 

>> t 

t = 

    7  8  9 14