0

基本上，我想创建字符串向量到整数向量的所有可能映射。我有以下内容：

std::vector<std::string> my_strings;
std::vector<unsigned int> my_ints;
my_strings.size() = 20; // not code, just for demonstration.
my_ints.size() = 4; // not code, just for demonstration.

std::vector<std::map<std::string, unsigned int> > all_possible_joint_mappings;

所以，我想填充 to 的所有all_possible_joint_mappings可能排列。有什么好的方法可以做到这一点？my_stringsmy_ints

一个示例联合映射将是：

string_1 -> int_1
string_2 -> int_1
string_3 -> int_1
string_4 -> int_4
string_5 -> int_2
...
string_20 -> int_3
4

3 回答 3

0

您只需遍历一个集合并在内部循环中遍历另一个集合：

std::vector<std::pair<std::string, unsigned int> > all_possible_joint_mappings;

for ( std::vector<std::string>::const_iterator s = my_strings.begin(); s != my_strings.end(); ++s )
{
    for ( std::vector<unsigned int>::const_iterator i = my_ints.begin(); i != my_ints.end(); ++i )
        all_possible_joint_mappings.push_back( std::make_pair( *s, *i ) );
    }
}

请注意，向量只需包含对来完成这项工作。

亲切的问候托尔斯滕

于 2012-07-13T17:59:39.580 回答
0

如果您想要从每个string值到多个int值的映射，并且您想要在单个容器中进行所有排列，那么请使用专门为此目的设计的容器类型 ( std::multimap)。这是一个例子：

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

int main()
{
   std::vector<std::string> strings;
   std::vector<int> ints;

   strings.push_back("One");
   strings.push_back("Two");
   strings.push_back("Three");
   strings.push_back("Four");
   strings.push_back("Five");

   ints.push_back(1);
   ints.push_back(2);
   ints.push_back(3);

   typedef std::multimap<std::string, int> SIMAP;
   SIMAP string_to_ints;

   std::for_each(
      strings.cbegin(),
      strings.cend(),
      [&ints, &string_to_ints] (const std::string& s)
   {
      std::for_each(
         ints.cbegin(),
         ints.cend(),
         [&] (const int i)
      {
         string_to_ints.insert(std::make_pair(s,i));
      });
   });

   std::for_each(
      string_to_ints.cbegin(),
      string_to_ints.cend(),
      [] (const SIMAP::value_type& mapping)
   {
      std::cout
         << mapping.first << " -> " << mapping.second << "\n";
   });

   return 0;
}
于 2012-07-13T18:35:26.133 回答
0

下面的代码将递归生成std::vector< std::vector<int> >所有 3 个字母的单词（按字典顺序），其中每个字母来自一个 4 个字母的字母表。有64 = 4^3这样的话。

请注意，一个简单的双循环是不够的，您需要对单词中的每个字母进行递归，并且对于每个字母，您都需要一个循环。总复杂度是O(K^N)针对字母字母表中的N字母单词K，而不是O(K*N)双循环。

它以一种直接的方式从 4 个字母的字母表中概括为 20 个字母的单词（尽管那是 2^40 = 1e12 个不同的单词）。当然，将它们与您的原始字符串匹配是一种简单的方式。

#include <array>
#include <cstddef>
#include <vector>
#include <iostream>

template<typename T, int K, int N>
void generate_all_multisets(
    std::array<T, K> const& alphabet, 
    std::vector< std::vector<T> >& all_words, 
    std::vector<T>& current_word, 
    int current_letter
)
{
    if (current_letter == N) {
        all_words.push_back(current_word);
        for (auto k = 0; k != N; ++k) 
            std::cout << current_word[k];
        std::cout << "\n";
        return;
    }   

    auto const tmp = current_word[current_letter];
    for (auto letter = alphabet.begin(); letter != alphabet.end(); ++letter) {
        current_word[current_letter] = *letter;
        generate_all_multisets<T, K, N>(alphabet, all_words, current_word, current_letter + 1);
    }
    current_word[current_letter] = tmp; 
}

template<typename T, int K, int N>
void generate_all_words(
    std::array<T, K> const& alphabet, 
    std::vector< std::vector<T> >& all_words
)
{
    // first word
    std::vector<T> word(N, alphabet.front());
    generate_all_multisets<T, K, N>(alphabet, all_words, word, 0);
}

int main()
{
    std::array<int, 4> alphabet = { 1, 2, 3, 4};
    auto const word_length = 3; 

    std::vector< std::vector<int> > all_words;
    generate_all_words<int, 4, 3>(alphabet, all_words);
    return 0;
}

编辑：Ideone上的输出

于 2012-07-13T19:18:32.233 回答