c++ - 如何获取两个字符串的所有排列组合？

Question

我有两个词，我想获得这些词组合的所有排列。必须保留每个字符串中字符的相对顺序

看看这个例子:

Input= "abc", "mn"

Output= "abcmn", "abmnc", "amnbc", "mnabc", "mabcn", "manbc", "mabnc", "ambnc", "ambcn", "abmcn"

我搜索stackoverflow.com，实现了下面的代码，但是不行!

void print_towstring(const std::vector<int>& v, const std::string& s1, const std::string& s2)
{
    std::size_t i1 = 0;
    std::size_t i2 = 0;

    for (int i : v) {
        std::cout << ((i == 0) ? s1[i1++] : s2[i2++]);
    }
    std::cout << std::endl;
}

void towstring(const std::string& s1, const std::string& s2)
{
    std::vector<int> v(s1.size(), 0);

    v.insert(v.end(), s2.size(), 1);
    do
    {
        print_towstring(v, s1, s2);
    } while (std::next_permutation(v.begin(), v.end()));
}

int main(int argc, char *argv[])
{
    towstring("abc", "mn");
    return 0;
}

如何在 C++ 中编写排列组合算法？

Answer 1

我想你可以递归地做。基本上，在每个步骤中，您都会创建两个分支:一个是您将右侧字符串中的一个字母添加到您的字符串中，另一个是您添加左侧字符串中的第一个字母的分支:

    void AddNext(
      std::string const& left,
      std::string const& right,
      std::string const& current,
      std::vector< std::string >& results)
    {
      if (left.empty())
      {
        current.append(right);
        results.push_back(current);
        return;
      }
      else if (right.empty())
      {
         current.append(left);
         results.push_back(current)
         return;
      }
      else
      {
        AddNext(left, right.substr(1, right.size() -1), current + std::string(1, right[0]), results);
        AddNext(left.substr(1, left.size() -1), right, current + std::string(1, left[0]), results);
      }
}