c++ - 按类型算法组合列表

Question

我正试图在 C++ 中创建一个算法，它将为我提供一组列表项(以 map 格式输入)的所有可能组合。我想避免重复并确保涵盖所有可能的组合。为了简化示例，输入可能如下所示:

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");

我将这张 map 输入算法，它应该吐出一个包含所有可能组合的 vector (使用每种键类型之一):

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

它需要适用于任何字符串 vector 映射。到目前为止，我已经尝试并接近了，但我最终得到了重复的组合和遗漏的组合:

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);
  }