algorithm - 重复的递归排列

Question

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

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++ 中实现它

Answer 1

鉴于您希望输出 AAB 和 ABA，您正在寻找排列而不是组合。特别是，您正在寻找一组大小 k 的唯一排列，其中元素是从一组 n 标记中替换绘制的。组合数为 _n+k-1C_k 而排列数为 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;
}