无连续字母相同的排列数

Question

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

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

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

我的做法

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

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

有没有其他方法可以通过编程方式确定这一点？

注：

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

Answer 1

Python

Python 是最流行的开源（免费）语言之一，用于处理大数据所需的大型复杂数据集。它近年来变得非常流行，因为它既灵活又相对容易学习。与大多数流行的开源软件一样，它也有一个庞大而活跃的社区，致力于改进产品并使其受到新用户的欢迎。免费的 Code Academy 课程将带您在 13 小时内完成基础知识。

来源：

http://www.datasciencecentral.com/profiles/blogs/ten-top-languages-for-crunching-big-data https://www.continuum.io/why-python

Answer 2

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

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

Answer 3

这里有一些 Python 比你的方法更有效，但仍然是指数级的（抱歉，不知道 PHP）：

from collections import Counter


def instancekey(letters):
    return tuple(sorted(Counter(letters).values()))


memo = {}


def permcount(letters):
    if not letters:
        return 1
    key = instancekey(letters)
    count = memo.get(key)
    if count is None:
        count = 0
        for letter, lettercount in Counter(letters).items():
            rest = letters
            for i in range(lettercount):
                j = rest.find(letter)
                rest = rest[:j] + rest[j + 1:]
                if i % 2 == 0:
                    count += permcount(rest)
                else:
                    count -= permcount(rest)
        memo[key] = count
    return count

这里有两个想法。第一种是通过包含排除递归地执行计数。对于输入中的每个字母，我们累积以该字母开头的可能性的数量。天真地，计算剩余字母的可能性就足够了，但这并没有强制执行前两个字母相等的约束。因此，我们应用更正——减去两个字母被删除的可能性的数量。此更正本身需要更正，因此我们到达 inclusion-exclusion formula.

第二个想法是使用记忆来显着减少函数计算的次数。给定一个像 PQRDDDEEEEFFFFF 这样的词，我们数

P: 1
Q: 1
R: 1
D: 3
E: 4
F: 5

然后删除字母（因为它们无关紧要）并对值进行排序：

1,1,1,3,4,5.

Answer 4

纯方法就是暴力破解。只需以 N 为底计数，其中 N 是不同字母的数量。以 N 为基数所需的位数就是字母总数。然后对允许的每个字母的数量应用约束，并且不能有两个连续的相同。

它不漂亮也不快，但它会给出正确的答案。

这里是 PHP:

$letters = 'PQRDDDEEEEFFFFF';

$letter_counts = CountLetters($letters);

echo CountCombinations($letter_counts);

function CountLetters($letters) {
    $letter_counts = array();
    foreach (str_split($letters) as $letter) {
        if (isset($letter_counts[$letter])) {
            $letter_counts[$letter]++;
        } else {
            $letter_counts[$letter] = 1;
        }
    }
    return array_values($letter_counts);
}

function CountCombinations($allowable) {
    $max = count($allowable) - 1;
    $total_places = 0;
    for ($index = 0; $index <= $max; $index++) {
        $total_places += $allowable[$index];
    }

    $counter = array_fill(0, $total_places, 0);

    $combinations = 0;
    do {
        $ok = true;

        // count the number of each character in this combination
        $bins = array_fill(0, $max + 1, 0);
        for ($index = 0; $index < $total_places; $index++) {
            $bins[$counter[$index]]++;
        }

        // ensure the counts match the number allowable for each
        for ($index = 0; $index <= $max; $index++) {
            if ($bins[$index] != $allowable[$index]) {
                $ok = false;
                break;
            }

        }

        // ensure that no two consecutive are the same
        if ($ok) {
            for ($index = 0; $index <= ($total_places - 2); $index++) {
                if ($counter[$index] == $counter[$index + 1]) {
                    $ok = false;
                    break;
                }
            }
        }

        if ($ok) {
            $combinations++;
        }

        // find the next combination (i.e. count in base N)
        for ($index = 0; $index <= ($total_places - 1); $index++) {
            $counter[$index] = $counter[$index] + 1;
            if ($counter[$index] <= $max) {
                break;
            } else {
                $counter[$index] = 0;
            }
        }
    } while ($index < $total_places);

    return $combinations;
}

无连续字母相同的排列数

Number of arrangements with no consecutive letter the same

php

algorithm

permutation

heaps-algorithm