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

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