具有重复的递归排列

我正在尝试编写一个递归函数，该函数通过给定列表的重复来获取所有排列。

Eg. set = ABC
1. AAA
2. AAB
3. AAC
4. ABA 
N. CCC

我想要此代码的递归版本，以便我可以获得任何大小的集合的排列：

for i=0; i<S.size(); i++ {
   for j=0; j<S.size(); j++ {
      for k=0; k<S.size(); k++ {

         perm[0] = S[i];
         perm[1] = S[j];
         perm[2] = S[k];
         permutations.push(combo);

      }
   }
}

我在思考这个问题时遇到了一些困难。到目前为止，我认为我需要找到何时达到任意深度以停止重复诅咒。

编辑：我更喜欢伪代码解决方案，我没有在 C++ 中实现它

Given that you want both AAB and ABA to be output, you are looking for permutations rather than combinations. In particular, you are looking for the unique permutations of a set of size k where the elements are drawn with replacement from a set of n tokens. The number of combinations is _n+k-1C_k while the number of permutations is n^k.

说明这两个概念的伪代码：

build_combinations (tokens, set_size)
  Arrangements combos
  if (set_size == 0)
    combos.add ("")
  else
    Comment: tail_substrings of "ABC" is ("ABC", "BC", "C").
    foreach tail (tail_substrings (tokens))
      foreach sub_combo (build_combinations (tail, set_size-1))
        combos.add (tail.first() + sub_combo)
  return combos

build_permutations (tokens, set_size)
  Arrangements perms
  if (set_size == 0)
    perms.add ("")
  else
    sub_perms = build_permutations (tokens, set_size-1)
    foreach token (tokens)
      foreach perm (sub_perms)
        perms.add (cur_token + *rem_iter)
  return perms

一个有效的 C++ 实现：

#include <string>
#include <vector>

typedef std::string::const_iterator StringIterator;
typedef std::vector<std::string> Arrangements;
typedef Arrangements::const_iterator ArrangementsIterator;

Arrangements build_combinations (const std::string & tokens, unsigned set_size)
{
  Arrangements combos;
  if (set_size == 0) {
    combos.push_back ("");
  }   
  else {
    for (StringIterator token_iter = tokens.begin();
         token_iter != tokens.end();
         ++token_iter) {
      std::string cur_token(1, *token_iter);
      std::string rem_tokens(token_iter, tokens.end());
      Arrangements rem_combos = build_combinations (rem_tokens, set_size-1);
      for (ArrangementsIterator rem_iter = rem_combos.begin();
           rem_iter != rem_combos.end();
           ++rem_iter) {
         combos.push_back (cur_token + *rem_iter);
      }
    }
  }   
  return combos;
}   

Arrangements build_permutations (const std::string & tokens, unsigned set_size)
{
  Arrangements perms;
  if (set_size == 0) {
    perms.push_back ("");
  }
  else {
    Arrangements rem_perms = build_permutations (tokens, set_size-1);
    for (StringIterator token_iter = tokens.begin();
         token_iter != tokens.end();
         ++token_iter) {
      std::string cur_token(1, *token_iter);
      for (ArrangementsIterator rem_iter = rem_perms.begin();
           rem_iter != rem_perms.end();
           ++rem_iter) {
         perms.push_back (cur_token + *rem_iter);
      }
    }
  }
  return perms;
}