7

我想用 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

输出：

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。

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

这是为了学习目的，不是家庭作业。我希望我的家庭作业是这样的。

4

3 回答 3

5

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

只需在基数转换上进行搜索，实现从每个“数字”到相应字符的映射，然后简单地执行一个从 0 到 word_length字母大小的 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
于 2010-06-11T21:21:40.340 回答
1

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

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

于 2010-06-11T21:49:46.867 回答
0

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;
 }
于 2017-02-25T10:05:22.363 回答