What I'm hoping to get as an answer:

我希望有人能告诉我解决这些类型问题的算法的一般类别 . 理想情况下，算法可以并行运行，但我仍然对只能按顺序执行的算法非常感兴趣 . 非常感谢具体的算法名称或参考文献:)

What I've done so far:

我基本上使用一些暴力方法来解决这个问题，包括生成给定字符串长度的所有排列，然后过滤掉与规则集不匹配的排列 . 我不喜欢这种方法，因为它显然非常慢并且很快就受到我的计算能力（1台PC）和字符串大小的限制 . 我开始对这种方法进行很少的优化，但感觉我必须重新发明轮子，并且可能已经有一套算法来解决这些问题 .

问题描述：

考虑如下字符串：

ABCDBEACBDECDBAACBE

我正在尝试找出有效的方法来生成遵循一组规则/条件的字符串的所有排列 .

规则示例：

简单示例：

与原始字符串必须至少有2个不同之处
差异必须在字母集中（A，B，C，D，E）

鉴于上述规则，单个有效排列的一个例子是：

DE CDBEACBDECDBAACBE

复杂的规则集示例1：

与原始字符串必须至少有2个不同之处
差异必须在字母集中（A，B，C，D，E）
NEW: 差异必须出现在字符串的已定义索引范围内
NEW: 每个范围必须有2个不同

所以，给定原始字符串，假设我们定义了以下范围：

[（0,4），（8,14）]

这看起来像：

[ABCDB] EAC [BDECDBA] ACBE

一个有效的排列示例是：

BD CDBEACB AB CDBAACBE

复杂的规则集示例2：

与原始字符串必须至少有2个不同之处
差异必须在字母集中（A，B，C，D，E）
差异必须在字符串的已定义索引范围内发生
每个范围必须有2个差异
NEW: 差异必须是特定的组合，让我们说"AB"

范围：

[（0,4），（8,14）]

一个有效的排列示例是：

B AB DBEACB AB CDBAACBE

复杂的规则集示例3：

与原始字符串必须至少有2个不同之处
差异必须在字母集中（A，B，C，D，E）
差异必须在字符串的已定义索引范围内发生
每个范围必须有2个差异
NEW: 范围可以重叠

范围：

[（0,4），（3,7）]

这看起来像：

[ABCD [B] EAC] BDECDBAACBE

一个有效的排列示例是：

ABC ADB ACBDECDBAACBE

1 回答

1
建议的方法

我建议你阅读deterministic finite automaton .

我试图模拟这类问题的方法是将问题转变为一个状态机，它能够根据一次一个地输入字符来识别所需类型的字符串 .

拥有状态机后，您可以使用动态编程来计算可以通过在特定状态下启动而生成的匹配字符串的数量 . （州知道到目前为止已经生成了多少个字符，以及每个规则的进度 . ）

通过此动态编程的结果，您可以在时间O（n）中生成匹配字符串的按字典顺序排列的第k个示例，其中n是字符串的长度 .

但是，解决动态编程的成本会有很大差异，具体取决于规则集的复杂程度 .

示例

对于你的例子3：
```
There must be at least 2 differences from the original string
The differences must be in the alphabet set (A,B,C,D,E)
Differences must occur within defined index ranges of the string
Each range must have 2 differences
```
国家需要包括以下信息：
```
Number of differences in first range (0,1,2)
Number of differences in second range (0,1,2)
```
所以总共有9个州要建模 .

对于具有R范围的系统，每个系统需要D差异，将需要（D 1）^ R个状态（如果范围不重叠则更少） .
回复于 2024-05-04T05:52:04+08:00

根据规则生成字符串的变体

问题描述：

规则示例：

简单示例：

复杂的规则集示例1：

复杂的规则集示例2：

复杂的规则集示例3：

1 回答

建议的方法

示例

相关问题