c++ - 重复字母和连续字母不相同的排列

Question

我一直在尝试解决关于排列的问题，但并没有真正成功。我想生成指定长度的所有排列，这些排列以一个字母开头并以相同的字母结尾，并且连续的两个字母不应相同。生成的排列可以有重复的字母。
例如，
如果数组有 {a,b,c,d} 并且我想要所有以 a 开头和结尾的排列。
答案应该是:
阿布卡
阿布达
阿巴
阿达
如果数组是 {a,b,c,d,e}
输出:
阿布达
阿巴达
阿布卡
蕉麻
阿布达
阿卡达
阿克巴
阿卡巴
adbca
阿达卡
阿德巴
阿达巴
abcba
阿巴巴
阿巴
阿布卡
阿卡卡
阿迪卡
阿布达
ADCA
阿达达

我什至想知道是否有某种方法可以直接了解我将通过某些公式获得的数组的解数..
提前谢谢大家..

Answer 1

算法如下。你从某个字母 a 开始，然后有一组你接下来可以使用的所有字母。然后，对于集合中的每个元素，您将 a 展开为 ab ac 广告。然后，您将 a 加回到集合中，并为每个新词相应地从集合中删除 b、c、d。之后你做同样的事情(递归)。唯一棘手的部分是您即将完成的时候。然后，在选择倒数第二个字母之前，您还需要删除开始的字母。

关于数学公式:

让 T(n,l) 表示长度 l 和字母表大小 n 的“排列”数。现在我们可以设计以下递归:

T(n,3) = n - 1 // a(something other than a)a
T(n,k) = (n-1)^(l-2) - T(n, k-1)

在递归情况下会发生什么。我们从考虑最后一个字母和倒数第二个字母可能相等的情况开始。所以我们有 a(letter other than previous, so (n-1) choices)^(l-2) 最后我们减去第一个字母等于倒数第二个的情况，即 T(n, k-1).

要在计算机上高效地计算它，请使用动态编程或内存。