0

基本的に、文字列のベクトルから int のベクトルへのすべての可能なマッピングを作成したいと考えています。私は次のものを持っています：

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;

all_possible_joint_mappingsしたがって、 toのすべての可能な順列を入力しmy_stringsたいと思いmy_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

以下のコードは、すべての 3 文字の単語 (辞書式順序) を再帰的に生成しますstd::vector< std::vector<int> >。各文字は 4 文字のアルファベットに由来します。64 = 4^3そんな言葉があります。

単純な二重ループでは不十分であることに注意してください。単語の各文字を再帰する必要があり、文字ごとにループが必要です。全体の複雑さは- 文字O(K^N)のアルファベットNからの - 文字の単語であり、二重ループの場合とは異なります。KO(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 に答える
0

string各値から複数の値へのマッピングが必要intで、すべての順列を 1 つのコンテナーに格納する場合は、この目的のために特別に設計されたコンテナー タイプを使用します ( 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

1 つのコレクションを反復処理し、内側のループで他のコレクションを反復処理するだけです。

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 に答える