php - 无连续字母相同的排列数

Question

这个问题与我的问题here有关.我正在尝试以编程方式获取以下计数以验证我的数学是否正确。

How many arrangements of the letters in the word PQRDDDEEEEFFFFF have no consecutive letter the same?

如何使用 php 程序确定此计数？

我的方法

1. 使用堆算法生成所有可能的排列并存储在数组中(使用堆算法，因为它被发现速度更快)
2. 使用 array_unique 函数删除了所有重复项
3. 遍历数组，使用正则表达式/(.)\1/识别相邻字母相同的字符串，并将相邻字母不相同的字符串复制到新数组。
4. 新数组包含所需的元素列表。

我的方法运行良好。但是，对于大字符串(超过 10 个字符的字符串)，由于大量的排列会出现内存问题，因此程序无法运行。

是否有任何替代方法以编程方式确定这一点？

注意:

我只寻找计数而不是字符串列表

Answer 1

您可以将其重新定义为图形问题。该图将为您的集合“PQRDDDEEEEFFFFF”中的每个字母都有节点，并且不允许自循环路径回到相同的字母或代表相同字母的节点之间。然后，您将通过图形枚举所有长度为 15 的非循环路径。这应该会显着减少代码的内存占用，并且您不会生成任何包含需要丢弃的连续字母的“单词”。通过快速谷歌搜索，我在网上找到了几种不同的 php 图形遍历算法。您可以根据自己的目的快速调整一个。

要显着提高性能，您可以使用内存策略。即从一个“F”开始，来自其他“F”节点的排列是相同的，子路径也是如此。有一些带内存的骑士游算法也可以很好地适应这个问题。