如何通过字符串的重复生成所有变体？

Question

我想通过 C++ 中的字符串重复生成所有变体，并且我非常喜欢非递归算法。我过去提出了一种递归算法，但由于复杂性（r^n），我希望看到一种迭代方法。

我很惊讶我无法在网络或 StackOverflow 上找到此问题的解决方案。

我想出了一个Python脚本，它也能完成我想要的事情：

import itertools

variations = itertools.product('ab', repeat=4)
for variations in variations:
        variation_string = ""
        for letter in variations:
                variation_string += letter
        print variation_string

输出：

aaaa 啊阿布 阿巴 阿布 阿巴 阿巴布 阿爸 阿布 咩咩 巴布 巴巴 巴布 巴巴 巴巴布 BBBA bbbb

理想情况下，我想要一个可以产生精确输出、采用完全相同参数的 C++ 程序。

这是出于学习目的，不是家庭作业。我希望我的家庭作业也是这样的。

Answer 1

您可以将其视为计数，其基数等于字母表中的字符数（如果可以输入，请特别注意字母表中的多个相同字符）。例如，aaaa aaab aaba ... 示例实际上是数字 0-15 的二进制表示。

只需搜索基数转换，实现从每个“数字”到相应字符的映射，然后简单地执行从 0 到 word_length^{alphabet_size} 的 for 循环。

这样的算法应该在时间上与数字成线性比例地运行需要使用恒定内存量生成的字符串。

Java

public class Test {
    public static void main(String... args) {

        // Limit imposed by Integer.toString(int i, int radix) which is used
        // for the purpose of this demo.
        final String chars = "0123456789abcdefghijklmnopqrstuvwxyz";

        int wordLength = 3;
        char[] alphabet = { 'a', 'b', 'c' };

        for (int i = 0; i < Math.pow(wordLength, alphabet.length); i++) {

            String str = Integer.toString(i, alphabet.length);

            String result = "";
            while (result.length() + str.length() < wordLength)
                result += alphabet[0];

            for (char c : str.toCharArray())
                result += alphabet[chars.indexOf(c)];

            System.out.println(result);
        }
    }
}

输出演示：

aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc

Answer 2

这是一般配方，而不是特定于实现产品的 C++：

采用产品输入字符串 "abc.." 生成矩阵 "abc.."x"abc.."。 N^2 复杂度。
将矩阵表示为向量并重复乘以 "abc"，复杂度 (N^2)*N，重复。

Answer 3

next_variation 类似 STL 函数。接受任何类似数字类型的容器的迭代器。您也可以使用浮点数/双精度数。
算法本身非常简单。迭代器的要求是只能向前。甚至 std::list<...>可以使用。

template<class _Tnumber, class _Titerator >
 bool next_variation
  (
       _Titerator const& _First
     , _Titerator const& _Last
     , _Tnumber const& _Upper
     , _Tnumber const& _Start = 0
     , _Tnumber const& _Step  = 1
  )
  {
   _Titerator _Next = _First;
   while( _Next  != _Last )
    {
      *_Next += _Step;
     if( *_Next < _Upper )
      {
       return true;
      }
     (*_Next) = _Start;
     ++_Next;
    }
   return false;
  }

int main( int argc, char *argv[] )
 {
  std::string s("aaaa");
  do{
      std::cout << s << std::endl;
  }while (next_variation(s.begin(), s.end(), 'c', 'a'));

  std::vector< double > dd(3,1);
  do{
   std::cout << dd[0] << "," << dd[1] << "," << dd[2] << ","  << std::endl;
  }while( next_variation<double>( dd.begin(), dd.end(), 5, 1, 0.5 ) );

  return EXIT_SUCCESS;
 }