这个问题与我的问题here有关.我正在尝试以编程方式获取以下计数以验证我的数学是否正确。
How many arrangements of the letters in the word PQRDDDEEEEFFFFF have no consecutive letter the same?
如何使用 php 程序确定此计数？
我的方法
- 使用堆算法生成所有可能的排列并存储在数组中(使用堆算法，因为它被发现速度更快)
- 使用 array_unique 函数删除了所有重复项
- 遍历数组，使用正则表达式/(.)\1/识别相邻字母相同的字符串，并将相邻字母不相同的字符串复制到新数组。
- 新数组包含所需的元素列表。
我的方法运行良好。但是，对于大字符串(超过 10 个字符的字符串)，由于大量的排列会出现内存问题，因此程序无法运行。
是否有任何替代方法以编程方式确定这一点？
注意:
我只寻找计数而不是字符串列表
最佳答案
您可以将其重新定义为图形问题。该图将为您的集合“PQRDDDEEEEFFFFF”中的每个字母都有节点，并且不允许自循环路径回到相同的字母或代表相同字母的节点之间。然后，您将通过图形枚举所有长度为 15 的非循环路径。这应该会显着减少代码的内存占用，并且您不会生成任何包含需要丢弃的连续字母的“单词”。通过快速谷歌搜索，我在网上找到了几种不同的 php 图形遍历算法。您可以根据自己的目的快速调整一个。
要显着提高性能，您可以使用内存策略。即从一个“F”开始，来自其他“F”节点的排列是相同的，子路径也是如此。有一些带内存的骑士游算法也可以很好地适应这个问题。
关于php - 无连续字母相同的排列数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41063538/