2

有几种算法可以打印字符串的所有组合，但我需要一种以特定顺序打印它们的算法。目前我使用的标准排列算法类似于这个问题的最佳答案（不是问题本身）：C++ recursive permutation algorithm for strings -> not skipping duplicates

例如，对于输入“ABC”，输出将是：ABC ACB BAC BCA CAB CBA

对于输入“ACC”，它将是： ACC CAC CCA

输出都是正确的，但是我需要它们以不同的顺序。输入将仅包含字符“A”和“C”，为了方便起见，我在将字符串输入到递归函数之前按字母顺序对字符串进行排序，因此输入字符串将始终具有相同的字符（即 AACCC）。至于顺序，我想将“C”的集合视为一个单一的实体，我只将每个字符的排列集左移到第一个“C”的右侧。所以对于输入“ACC”，第一个输出是“ACC”，这是可以的，下一个输出应该是“CCA”，因为我将所有的'C'向左移动了一步，然后是所有字符的“CCA”的排列第一个“C”的右侧是最终输出，即“ACA”。

对于这些输入，我需要它看起来像这样：

输入：ACC

输出：ACC CCA CAC

输入：AACC

输出：

AACC ACCA ACAC CCAA CACA CAAC

知道我应该如何修改我的算法以按此顺序生成组合吗？

4

1 回答 1

0

对于具有两个不同字符A和的字符串C，给定n的是A's 的数量，听起来您正在寻找的是这些序列的串联：所有以完全n A's 开头的排列以相反的字典顺序，所有排列都以完全n-1 A是按字典顺序排列的，等等。因此，您可以采用按字典顺序排列的现有输出，并以相反的顺序对其进行迭代，选择匹配的元素/^A{n}C/，/^A{n-1}C/通过/^A{0}C/并将它们添加到新集合中。

A您可以通过生成从 ' 到零的每个长度的'字符串直接生成此输出n A，然后对于每个字符串，以相反的字典顺序附加剩余字符的排列。

于 2012-11-10T22:00:02.373 回答