반복이없는 다중 벡터 요소의 조합

Question

벡터의 양이 n, 예를 들어 3이고 n 요소가 (반드시 같은 양 일 필요는 없음) 있습니다. 나는 그 (것)들 사이 x 조합의 양을 선택할 필요가있다. 벡터 [n]에서 2를 선택하는 것과 같습니다. 예 : V1 추천 한 벡터 자체

std::vector<int> v1(3), v2(5), v3(2); 

있을 수없는 조합 [0] V1 [1]. 어떻게해야합니까? 나는 모든 것을 시도했지만 이것을 알아낼 수는 없습니다.

Answer 1

내가 제대로 이해 경우 N 벡터를 가지고, 요소 다른 수의 (와 각각의 크기를 호출 i 번째 벡터 Si)와 반복없이 이러한 벡터로부터 요소의 M 개의 조합을 선택해야합니다. 각 조합은 N 개의 요소가되며, 각 벡터의 요소 중 하나입니다. 이 경우

는 가능한 순열의 수는 벡터의 크기의 제품입니다 ++ 나는 P를 호출하고 C에서 계산됩니다 설정 방정식의 어떤 형태의 부족, 이는 : 그래서

std::vector<size_t> S(N); 
// ...populate S... 
size_t P = 1; 
for(size_t i=0;i<S.size();++i) 
    P *= S[i]; 

이제 문제는 0과 P-1 사이의 M 개의 고유 번호를 선택하고, 그 각각의 M 번호를 N 개의 색인으로 변환하여 원래 벡터로 변환하는 것입니다. M 번호를 계산하는 몇 가지 방법을 생각해 볼 수 있습니다. 아마도 가장 쉬운 방법은 M 개의 다른 숫자를 얻을 때까지 난수를 그려 두는 것입니다.

약간 더 복잡한 부분은 각 M 번호를 인덱스 벡터로 바꾸는 것입니다. 당신이 1 차원 배열로 표현되는 2 차원 배열을 인덱싱 할 때 훨씬처럼 우리는 기본적으로 각 인덱스에 대한 조각으로 m의 최대 갈비

size_t m = /* ... one of the M permutations */; 
std::vector<size_t> indices_m(N); 

for(size_t i=0; i<N; ++i) 
{ 
    indices[i] = m % S[i]; 
    m /= S[i]; 
} 

이 작업을 수행 할 수 있습니다. 이제 우리는 우리가

V1 [인덱스 [0] v2와 함께 우리의 순열의 3 개 요소를 얻을 수있는 N = 3 예를 가지고가는 경우에

[인덱스 [1]] V3 [인덱스 [2]

은 m만큼의 고유 한 값을 필요에 따라 생성합니다.

Answer 2

아마 혼란은 문제의 부적절한 정의로 인해 발생합니다. N 시간은 V 벡터의 1에서 1 개 요소를 선택하는 당신이 필요로하는 것을 추측, 당신은이 작업을 수행 할 수 있습니다

select N of the V vectors you want to pick from (N <= V) 
for each of the selected vectors, select 1 of the vector.size() elements.