형식 알고리즘에 의한 목록 조합

Question

C++에서 목록 항목 집합 (지도 형식으로 입력)의 가능한 모든 조합을 제공하는 알고리즘을 만들려고합니다. 나는 중복을 피하고 모든 가능한 조합을 포함하고 싶다. 내가 알고리즘에이지도를 공급 것

map<string, vector<string> > sandwichMap; 

sandwichMap["bread"].push_back("wheat"); 
sandwichMap["bread"].push_back("white"); 
sandwichMap["meat"].push_back("ham"); 
sandwichMap["meat"].push_back("turkey"); 
sandwichMap["meat"].push_back("roastbeef"); 
sandwichMap["veggie"].push_back("lettuce"); 
sandwichMap["sauce"].push_back("mustard"); 

, 그리고 각 키 유형 중 하나를 사용하여 가능한 조합 (모두와 벡터를 뱉어해야한다 : 예를 단순화하기 위해, 여기에 같은 입력이 보일 수 있습니다 무엇) :

wheat+ham+lettuce+mustard 
wheat+turkey+lettuce+mustard 
wheat+roastbeef+lettuce+mustard 
white+ham+lettuce+mustard 
white+turkey+lettuce+mustard 
white+roastbeef+lettuce+mustard 

모든 문자열 벡터 맵에서 작동해야합니다. 지금까지 시도했지만 가까이에 있지만 중복 조합과 놓친 조합이 생깁니다.

sandwichList getCombinations(sandwichMap sMap) 
{ 
    locList retList; 
    int totalCombos = 1; 

    for (sandwichMapIt i = sMap.begin(); i != sMap.end(); ++i) 
    { 
     totalCombos *= i->second.size(); 
    } 

    retList.resize(totalCombos); 
    int locCount; 

    for (sandwichMapIt a = sMap.begin(); a != sMap.end(); ++a) 
    { 
     locCount = 0; 
     for (locListIt l = a->second.begin(); l != a->second.end(); ++l) 
     { 
      for (unsigned int i = 0; i < totalCombos/a->second.size(); ++i) 
      { 
       retList[i + a->second.size() * locCount] += *l; 
      } 

      locCount++; 
     } 
    } 

    return retList; 
} 

어떤 도움을 주시면 감사하겠습니다!

업데이트 코드 :

#include <vector> 
#include <map> 
#include <list> 
#include <iostream> 

typedef std::vector<std::string> strVec; 
typedef std::list<std::string> strList; 
typedef std::map<std::string, strVec> sandwichMap; 

int main() 
{ 
    sandwichMap sMap; 

    sMap["bread"].push_back("wheat"); 
    sMap["bread"].push_back("white"); 
    sMap["meat"].push_back("ham"); 
    sMap["meat"].push_back("turkey"); 
    sMap["meat"].push_back("roastbeef"); 
    sMap["veggie"].push_back("lettuce"); 
    sMap["sauce"].push_back("mustard"); 

    strList finalSandwichList; 
    for (sandwichMap::iterator i = sMap.begin(); i != sMap.end(); ++i) 
    { 
     strList tmpSandwich; 
     for (strVec::iterator j = i->second.begin(); j != i->second.end(); ++j) 
     { 
      if (finalSandwichList.empty()) 
      { 
       tmpSandwich.push_back(*j); 
      } 
      else 
      { 
       for (strList::iterator k = finalSandwichList.begin(); k != finalSandwichList.end(); ++k) 
        tmpSandwich.push_back(*k + "+" + *j); 
      } 
     } 
     tmpSandwich.swap(finalSandwichList); 
    } 

    for (strList::iterator i = finalSandwichList.begin(); i != finalSandwichList.end(); ++i) 
    { 
     std::cout << *i << std::endl; 
    } 

    return 0; 
} 

Answer 1

//solution 
    std::list<std::string> result; 
    for(auto i=sandwichMap.begin(); i!=sandwichMap.end(); ++i) { 
    std::list<std::string> new_result; 
    for(auto j=i->second.begin(); j!=i->second.end(); ++j) { 
     if(result.empty()) 
     new_result.push_back(*j); 
     else 
     for(auto k=result.begin(); k!=result.end(); ++k) 
     new_result.push_back(*k + "+" + *j); 
    } 
    new_result.swap(result); 
    } 

Answer 2

이 작동합니다 : 나는 가능한 모든 조합을 평가하기 위해 되돌아 사용했다

#include<iostream> 
#include<map> 
#include<string> 
#include<algorithm> 

using namespace std; 

map<string, vector<string>> sMap; 
vector<string> add; 
int sett[200], countt; 

void solve(map<string, vector<string>>::iterator itt, int ct, vector<string> addd){ 
    vector<string> tmp = itt->second; 
    if(ct == countt){ 
     for(int j=0;j<addd.size();j++){ 
      cout<<addd[j]<<" "; 
     } 
     cout<<endl; 
     return; 
    } 
    itt++; 
    for(int i=0;i<tmp.size();i++){ 
     //cout<<tmp[i]<<" "; 
     addd.push_back(tmp[i]); 
     solve(itt, ct+1, addd); 
     vector<string>::iterator tempIt = addd.end(); 
     addd.erase(tempIt--); 
    } 
} 

int main(){ 
    sMap["bre"].push_back("wh"); 
    sMap["bre"].push_back("whi"); 
    sMap["me"].push_back("ham"); 
    sMap["me"].push_back("tur"); 
    sMap["me"].push_back("rr"); 
    sMap["veg"].push_back("let"); 
    sMap["sau"].push_back("mus"); 
    countt = sMap.size(); 
    solve(sMap.begin(), 0, add); 
return 0; 
} 

. 참고 : 당신이 C++ 출력

이

링크의 낮은 버전에 대한 코드의 일부를 변경해야 할 수도 있습니다 (11) C++에 있습니다, http://ideone.com/Ou2411

Answer 3

코드 때문에 도우미 메서드의 긴 좀 있지만 이 작업을 수행합니다지도가 반복적으로 갈 너무 큰 경우 generate_all(sMap.begin(),aVector,sMap);

와

#include <vector> 
#include <string> 
#include <map> 
#include <iostream> 
using namespace std; 

template <class T> 
vector<T> Head(const vector<T> &v) { 
    return vector<T>(v.begin(), v.begin() + 1); 
} 

template <class T> 
vector<T> Tail(const vector<T> &v) { 
    auto first = v.begin() + 1; 
    auto last = v.end(); 
    return vector<T>(first, last); 
} 

template <class T> 
vector<T> Concat(const vector<T> &v1, const vector<T> &v2) { 
    vector<T> result = v1; 
    result.insert(result.end(), v2.begin(), v2.end()); 
    return result; 
} 


vector<vector<string>> CombineVectorWithScalar(const vector<vector<string>> &v, const string &scalar) { 
    vector<vector<string>> result = v; 
    for (unsigned i = 0; i < v.size(); i++) { 
     result[i].push_back(scalar); 
    } 
    return result; 
} 

vector<vector<string>> CombineVectorWithVector(const vector<vector<string>> &v1, const vector<string> &v2) { 
    if (v2.empty()) { 
     return vector<vector<string>>(); 
    } 
    else { 
     auto headCombination = CombineVectorWithScalar(v1, v2.front()); 
     auto tailCombination = CombineVectorWithVector(v1, Tail(v2)); 
     return Concat(headCombination, tailCombination); 
    } 
} 

vector<string> GetKeys(const map<string, vector<string>> &mp) { 
    vector<string> keys; 

    for (auto it = mp.begin(); it != mp.end(); ++it) { 
     keys.push_back(it->first); 
    } 

    return keys; 
} 

vector<vector<string>> CombineMapValues(const map<string, vector<string>> &mp) { 
    vector<string> keys = GetKeys(mp); 

    vector<vector<string>> result; 
    auto &firstVector = mp.begin()->second; 
    for (auto it = firstVector.begin(); it != firstVector.end(); ++it) { 
     vector<string> oneElementList; 
     oneElementList.push_back(*it); 
     result.push_back(oneElementList); 
    } 

    vector<string> restOfTheKeys = Tail(keys); 
    for (auto it = restOfTheKeys.begin(); it != restOfTheKeys.end(); ++it) { 
     auto &currentVector = mp.find(*it)->second; 
     result = CombineVectorWithVector(result, currentVector); 
    } 

    return result; 
} 

void PrintCombinations(const vector<vector<string>> & allCombinations) { 
    for (auto it = allCombinations.begin(); it != allCombinations.end(); ++it) { 
     auto currentCombination = *it; 
     for (auto itInner = currentCombination.begin(); itInner != currentCombination.end(); ++itInner) { 
      cout << *itInner << " "; 
     } 
     cout << endl; 
    } 
} 

int main() { 
    map<string, vector<string> > sandwichMap; 

    sandwichMap["bread"].push_back("wheat"); 
    sandwichMap["bread"].push_back("white"); 
    sandwichMap["meat"].push_back("ham"); 
    sandwichMap["meat"].push_back("turkey"); 
    sandwichMap["meat"].push_back("roastbeef"); 
    sandwichMap["veggie"].push_back("lettuce"); 
    sandwichMap["sauce"].push_back("mustard"); 

    auto allCombinations = CombineMapValues(sandwichMap); 
    PrintCombinations(allCombinations); 

    return 0; 
} 

Answer 4

void generate_all(std::map<std::string,std::vector<std::string>>::iterator start, 
std::vector<std::string::iterator> accomulator, 
std::map<std::string,std::vector<std::string>>& sMap){ 
    for (auto it=start; it!=sMap.end(); ++it){ 
     for (auto jt=it->second.begin(); jt!=it->second.end(); jt++){ 
      generate_all(start+1,accomulator.pus_back[jt],sMap); 
     } 
    } 
    if (accomulator.size() == sMap.size()){ 
     // print accomulator 
    } 
} 

전화, 당신은 ALWA 수 있습니다 ys는 동일한 반복 코드를 생성합니다.

Answer 5

이 해결 방법은 재귀가 아닙니다. 기본적으로 그것이 무엇을하면 다음과 같다 : 많은 조합이 실제로

지도에서 각 키에 대해 알고 가능 얼마나

• 계산하면 총 그들의 nrCombinations/nrItemsInKey을 추가해야 할 것입니다.
• 나무가 자라는 것을 볼 수 있습니다. 방문한 키가 갈수록 더 많이 나타납니다.
• 몇 개가 있는지 추적하면 간격과 시작 위치가 자동으로 모든 조합을 채울 수 있습니다.

코드

#include <vector> 
#include <iostream> 
#include <map> 
#include <string> 

int main() { 
    std::map<std::string, std::vector<std::string> > sandwichMap; 

    sandwichMap["bread"].push_back("wheat"); 
    sandwichMap["bread"].push_back("white"); 
    sandwichMap["meat"].push_back("ham"); 
    sandwichMap["meat"].push_back("turkey"); 
    sandwichMap["meat"].push_back("roastbeef"); 
    sandwichMap["veggie"].push_back("lettuce"); 
    sandwichMap["sauce"].push_back("mustard"); 
    sandwichMap["sauce"].push_back("mayo"); 

    // Compute just how many combinations there are 
    int combinationNr = 1; 
    for (auto it : sandwichMap) { 
     combinationNr *= it.second.size(); 
    } 
    std::vector<std::vector<std::string>> solutions(combinationNr); 
    // We start with empty lists, thus we only have one cluster 
    int clusters = 1, clusterSize = combinationNr; 
    for (auto category : sandwichMap) { 
     int startIndex  = 0; 
     int itemsNr   = category.second.size(); 
     int itemsPerCluster = clusterSize/itemsNr; 
     for (auto item : category.second) { 
      for (int c = 0; c < clusters; ++c) { 
       for (int i = 0; i < itemsPerCluster; ++i) { 
        // We sequentially fill each cluster with this item. 
        // Each fill starts offset by the quantity of items 
        // already added in the cluster. 
        solutions[startIndex+i+c*clusterSize].push_back(item); 
       } 
      } 
      startIndex += itemsPerCluster; 
     } 
     clusters *= itemsNr; 
     clusterSize = combinationNr/clusters; 
    } 

    for (auto list : solutions) { 
     for (auto element : list) { 
      std::cout << element << ", "; 
     } 
     std::cout << "\n"; 
    } 
    return 0; 
}