如何计算与一组子集匹配的某些字符串的排列数？
How can I count the number of permutations of some string matching a set of subsets?
我有一个字符串S和一组S的排列子集，称为M。M的元素限制了S的允许排列。我想计算S的允许排列的数量。唯一的限制是M的允许元素是包含的子集对应于某些排列的开始或结束。
例如，假设 S='ABC' 和 M = {'AB', 'BC'}。因此，'ABC' 唯一允许的排列是 'ABC' 和 'CBA'。
我已经尝试从多个不同的方向来解决这个问题，但如果不枚举 S 的所有排列，我无法弄清楚如何解决它。任何人都可以提供任何见解吗？
利用Inclusion-exclusion principle.
在提供的示例中，它将是：
number of permutations that contain "AB" +
number of permutations that contain "BC" -
number of permutations that contain both "AB" and "BC"
你只需要实现一个函数来计算包含 all 给定子序列的排列数。
请注意，如果存在包含相同字母的子序列：
- 您可以组合子序列，例如两个子序列 "ABCD" + "CDEF" -> 一个子序列 "ABCDEF"
- 如果存在不匹配，则没有符合条件的排列。
一旦你得到了不同字母的子序列，结果就是阶乘（长度（S）-所有子序列的总长度+子序列的数量）。
您可以通过记住子集的组合子序列来优化它。
复杂度：2^|M| * (|S| + |M|)。
我有一个字符串S和一组S的排列子集，称为M。M的元素限制了S的允许排列。我想计算S的允许排列的数量。唯一的限制是M的允许元素是包含的子集对应于某些排列的开始或结束。
例如，假设 S='ABC' 和 M = {'AB', 'BC'}。因此，'ABC' 唯一允许的排列是 'ABC' 和 'CBA'。
我已经尝试从多个不同的方向来解决这个问题，但如果不枚举 S 的所有排列，我无法弄清楚如何解决它。任何人都可以提供任何见解吗？
利用Inclusion-exclusion principle.
在提供的示例中，它将是：
number of permutations that contain "AB" +
number of permutations that contain "BC" -
number of permutations that contain both "AB" and "BC"
你只需要实现一个函数来计算包含 all 给定子序列的排列数。
请注意，如果存在包含相同字母的子序列：
- 您可以组合子序列，例如两个子序列 "ABCD" + "CDEF" -> 一个子序列 "ABCDEF"
- 如果存在不匹配，则没有符合条件的排列。
一旦你得到了不同字母的子序列，结果就是阶乘（长度（S）-所有子序列的总长度+子序列的数量）。
您可以通过记住子集的组合子序列来优化它。
复杂度：2^|M| * (|S| + |M|)。