재정렬 된 큰 행렬에서 재정렬 된 벡터의 색인 찾기

Question

A 행렬을 가지고 있다고 가정합니다.이 행렬은 MATLAB에서 A = nchoosek(1:100, 6)을 사용합니다. 따라서 A는 재정렬되어 100

A 1 내지 6 자리를 선택하는 기준으로 모든 조합을 의미하며, 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 

그런 다음 A의 멤버 인 다른 재정렬 된 벡터 B이 있습니다. 예 : B=[5 10 11 40 51 67];

그래서 가장 빠른 방법을 사용하여 B의 색인을 찾는 방법은 주문 정보를 사용하는 것을 의미합니까 ??

Answer 1

A 행이 어떻게 생성되는지 유의해야합니다. 나는 이것이 문서에 명시되어 있지 않다고 생각한다. 아마도 너무 많이 의존해서는 안된다. 이것이 의미하는 바는 기술적으로 문서화되지 않은 동작이며 모든 버전에서 변경 될 수 있습니다.

그러나 각 요소는 끝 색인에서 시작하여 반복되고 모든 조합은 정렬됩니다. 이것은 당신이

B = [5 10 11 40 51 67]; 

첫 번째 인덱스는 4로 시작하는 모든 요소가 열거 된 것을 의미한다, 5 년, 처음부터 시작해야한다는 것을 의미한다. 그 중 몇 개입니까? 우리 등

제 수가 2 인 경우 (5)로부터 선택 가능한 98, 첫 번째 요소가 1이면 5를 선택할 99 개 번호를 갖기 때문에

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 

는 다음 [5 9 97 98 99 100] 통해 소자들 [5 6 7 8 9 10] 온다. 두 번째 요소가 해결 된 경우 다시 말하지만,이, 전체 조합입니다 :

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 

등등, 당신이 nchoosek(100-50,6-5)의 마지막 단어를 포함하는 [5 10 11 40 50 .] 모두를 구축 할 때까지. 그러면 남은 요소는 [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