1

我一直在尝试解决一个关于排列的问题，但并没有真正成功。我想生成以一个字母开头并以相同结尾的所有指定长度的排列，并且没有两个连续的字母应该是相同的。生成的排列可以有重复的字母。
例如，
如果数组有 {a,b,c,d} 并且我想要所有以 a 开头和结尾的排列。
答案应该是：
abca
abda
acba
acda
如果数组是 {a,b,c,d,e}
输出：
abcda
abada
abdca
abaca
acbda
acada
acdba
acaba
adbca
adaca
adcba
adaba
abcba
ababa
abdba
acbca
acaca
acdca
adbda
adcda
adada

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

4

3 回答 3

0

算法如下。您从某个字母 a 开始，然后有一组您可以使用的所有字母。然后对于集合中的每个元素，您将 a 扩展为 ab ac 广告。然后为每个新单词添加 a back 并从 set 中删除 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).

为了在计算机上有效地计算它，请使用动态编程或记忆。

于 2013-04-13T07:58:40.503 回答
0

首先，也许你应该把你的问题一分为二。一个用于堆栈交换的“数学”部分，一个用于可能性的数量，另一个用于使用算法生成它。

数学答案：

如果我理解正确，您希望您的字符串以某个字母开头，例如“a”。然后排列的数量取决于您生成的数组的大小。对于您描述的问题，您需要将您的字符串理解为“a* a”，其中“ ”可以采用多个值。一颗星可以用 26 种方式填写（字母表中的字母数）减去不符合规则的字母数。因此，第一颗星最多有 25 种可能性（因为您不能在两个连续字符中重复“a”）。第二颗星只能有 24 种可能性，因为它不能是“a”或它前面的字母（26-2=24）。然后，当我们组合可能性时，您就有 25*24 组合。

使用大小为 n 个字符的字符串（不包括从头开始设置的第一个和最后一个），您有 25^(n-1)*24 个组合。

对于算法部分：

请参阅回溯，以获得一种易于实施且非常快速的方式来生成您需要的内容。您只需遍历您的字符串并将那些未知字符（*s）设置为不重复相同字母的值，依此类推，直到您生成所有值。

从你的问题的措辞方式来看，我认为你的问题是某种家庭作业，所以如果你编写自己的算法而不是使用 STL 等会更好。

于 2013-04-13T08:10:15.830 回答
-1

您可以使用 STL 中的 next_permutation 算法

#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
char mychars[] = "abc";;

std::sort (mychars,mychars+3);

std::cout << "The 3! possible permutations with 3 elements:\n";
do {
  std::cout << mychars[0] << ' ' << mychars[1] << ' ' << mychars[2] << '\n';
} while ( std::next_permutation(mychars,mychars+3) );

std::cout << "After loop: " << mychars[0] << ' ' << mychars[1] << ' ' << mychars[2] << '\n';

return 0;

参考——http: //www.cplusplus.com/reference/algorithm/next_permutation/强文本

于 2013-04-13T07:54:28.920 回答