c - 以特定顺序获取字符串组合的递归算法

Question

有几种算法可以打印字符串的所有组合，但我需要一种可以按特定顺序打印它们的算法。目前我使用的是标准排列算法，类似于这个问题的最佳答案(不是问题本身)中的算法: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 中国民航

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

Answer 1

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

您可以通过生成 A 的字符串直接生成此输出来自 n 的每个长度的A的为零，然后对于每一个，以逆字典顺序追加剩余字符的排列。