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

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 作为输入的算法来解决，因为该数据还不够。您需要实际的有向图集而不是它的大小。

考虑两个类似的问题。两者都有 2 个字母的字母表（a、b）和 N = 3，但禁止的二合字母集不同。

问题#1

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

baa
bba
bbb

所以有3个解

问题#2

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

aba
bab

只有2个解。

发生这种情况是因为二合字母 aa 和 ab 的交互方式不同于二合字母 aa 和 bb。特别是aa和bb没有同时过滤掉三元组，但是aa和ab都过滤掉了三元组aab如此有效少了一个三联体被过滤掉了。

我认为可行的方法是在控制当前最后一个字符的字符串长度上使用 dynamic programming。

更新（算法草图）

让我们尝试将其作为 dynamic programming 字符串长度问题来解决。作为状态，我们想要保留的是以每个字符结尾的字符串的数量（因此是一个大小为 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).

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

How to calculate the amount of possibles sets of strings with elements of differents lenghts?

python

math

mathematical-optimization