목록 항목의 조합 찾기

Question

항목이있는 입력 목록이 있습니다. 이제 원본 inputLists에있는 항목의 모든 조합을 포함하는 resultLists (길이 n)를 계산하려고합니다 (각 inputList의 한 항목 가져옴).

나는 내가 여기 예를 제공해야한다고 생각 (N = 3) :

inputList1: [item1, item2, item3] 
inputList2: [item4] 
inputList3: [item5, item6] 

resultList1: [item1, item4, item5] 
resultList2: [item1, item4, item6] 
resultList3: [item2, item4, item5] 
resultList4: [item2, item4, item6] 
resultList5: [item3, item4, item5] 
resultList6: [item3, item4, item6] 

내가 바보의 종류를 느낄 수있어,하지만 난 방법을 구현하는 방법 (C++를) 함수에 대한 결과를 만드는 아무 생각이 없다 임의의 n 및 임의의 inputList 길이. 나는 어떤 종류의 재귀를 사용해야한다고 생각하지만 어떻게해야할지 모르겠다.
아이디어가 있으십니까? 의사의

Answer 1

일반적인 아이디어 :

vector<item> List1, List2, List3; 
// fill the lists 

vector<item> v; 
vector<vector<item>> results; 

for each item i in List1 
{ 
    v.push_back(i) 
    for each item j in List2 
    { 
     v.push_back(j); 
     for each item k in List3 
     { 
      v.push_back(k); 
      results.push_back(v); 
      v.pop_back(); 
     } 
     v.pop_back(); 
    } 
    v.pop_back(); 
} 

이 목록의 변수 수에 이렇게하려면, 내가 재귀 접근 방식으로 갈 것. 각 for 루프는 재귀 함수 호출로 대체됩니다. 이 함수는 inputList의 목록, 결과 목록 및 중간 결과 (위 예제에서 v)를 매개 변수로 저장하는 컨테이너를 허용해야합니다.

희망이 있습니다.

Answer 2

반복자는 여기에 친구입니다. 제로 크기의 목록이나 좋아하는 같은 오류 검사 또는 코너의 경우에 대해 귀찮게하지 않고 두 의사 버전 :

struct cartesian_product_iterator { 
    int indexes[n] initialized to zeroes 
    operator++() { 
     a = 0 
     indexes[a]++; 
     while a < n and indexes[a] >= list[a].size() 
      indexes[a] = 0 
      a++; 
    } 
    operator *() { 
     list<?> ret; 
     for a in 0..n-1: 
      ret.push_back(list[a][indexes[a]]); 
     return ret; 
    } 
    past_the_end_iterator() { indexes[n-1] = list[n-1].size(); } 
} 

당신은 indexes 배열이 여러 기지에 정수의 단지 분해 것을 알 수 있습니다.

struct cartesian_product_iterator_2 { 
    unsigned_or_arbitrarly_big_int a_large_number = 0; 
    operator ++() { a_large_number++; } 
    operator *() { 
     list<?> ret; 
     unsigned_or_arbitrarly_big_int to_decompose = a_large_number; 
     for a in 0..n-1: 
      index = to_decompose % list[a].size(); 
      to_decompose /= list[a].size(); 
      ret.push_back(list[a][index]); 
     } 
     return ret; 
    } 
    past_the_end_iterator() { 
     a_large_number = 1; 
     for each l in list: 
      a_large_number *= l.size(); 
    } 
} 

어떤 것이 가장 좋고/더 빠르 냐고 나는 정말로 생각하지 않습니다.