如何计算具有不同长度元素的字符串可能集的数量？

Question

我需要编写一个算法来计算给定一些限制的可能字符串的数量：

The strings must have an N amount of characters;
The strings only have an X number of different letters;
The strings can't have an Y number of digraphs;

例如，对于N= 2，X=3和Y= 6：

The string: _ _ _
My set of letters: {a, b, c}
Set of proibited digraphs: {aa, bb, cc, ab, ac, bc}
#The proper result is 1, but I'm getting -9

到目前为止，我的代码只有在字符串长度只有2的情况下才能正常工作。我无法生成一个蛮力算法，因为字符串长度可以小于10^9

这是我的密码：

def  arrangements(sizeOfSet, numberOfElements, isDigraph):

  if isDigraph:
    return pow(numberOfElements, sizeOfSet - 1)
    #sizeOfSet is subtracted by 1 cause digraphs occupies 2 spaces

  return pow(numberOfElements, sizeOfSet)

然后我从独立有向图集的排列中减去我的一组字母的排列。

Answer 1

这是一种评论，但对评论来说太大了。

不幸的是，我认为以N、X和Y作为输入的算法无法解决这个问题，因为这些数据是不够的。您需要的是实际的有向图集，而不是其大小。

考虑两个类似的问题。这两个字母都有两个字母(a，b)和N = 3，但是禁止的有向图的集合是不同的。

问题#1

我们禁止aa和ab。所以所有允许的三胞胎是：

• baa
• bba
• bbb

所以有三种解决方案

问题#2

我们禁止aa和bb。所以所有允许的三胞胎是：

• aba
• bab

只有2种解决方案。

这是因为有向图aa和ab的交互方式不同于有向图aa和bb。特别是，aa和bb没有同时过滤出三重态，但是三重态aab被aa和ab过滤掉，从而有效地减少了一个三重态。

我认为可以使用动态规划来控制字符串的长度，这是当前的最后一个字符。

更新(算法草图)

让我们尝试将其作为字符串长度的动态规划问题来解决。作为状态，我们想要保持的是以每个字符结尾的字符串数量(因此是大小为X的数组，或相同大小的字典)。如果我们找到了更新每个下一个字符串大小的状态的方法，那么当我们到达N时，我们可以对数组上的值进行求和，这将是我们的最终答案。

更新状态很容易。让我们考虑一下，当我们向长度为n-1的有效字符串添加一个新字符时会发生什么。我们得到一个长度为n的新的有效字符串，除非最后一对是禁止的有向图之一。因此，构建新的状态很容易(这里是Python风格的伪代码)：

for prev_last_char in chars:
    for new_last_char in chars:
        if (prev_last_char, new_last_char) not in prohibited: 
             new_state[new_last_char] += old_state[prev_last_char]

显然，初始状态是数组(或字典)，每个字符都包含1。

假设prohibited访问时间是O(1)，使用基于哈希的字典应该是可以实现的，那么一个步骤的复杂性就是O(X*X)。因此，总的算法复杂度为O(X^2*N)。