反复搜索替换直到收敛

Question

我正在搜索以下问题的名称和有效解决方案：假设我有一个字符串 s='abcdef' 和一组 find/replace 规则 Pn

P1: ab -> xy
P2: xyc -> 123
P3: ef -> ab

将这些规则依次应用于 s 我可以得到以下字符串：

1. xycdef
2. 123def
3. 123dab
4. 123dxy

我的目标是达到 "stable" 已应用所有（大多数？）规则的状态（此处：123dxy）。

所以我的问题是，是否有明确定义的方法来处理此类问题？是否对规则有一般约束以避免无限循环（例如，ab -> xy、xy -> ab）。有没有办法确定最大迭代次数的界限？

任何指向相关 concepts/related 工作的指针都将受到赞赏。

Answer 1

我会将其转化为图形问题。
在你的例子中，我会有一个名为 ab 的节点，另一个 xy，xyc，等等
根据规则，节点之间存在有向边。
这里：V={ab, xy, xyc, 123, ef}; E={(ab,xy), (xyz.123), (ef, ab)}

基本检查：
如果在这个阶段你的图表中有循环，那么你就有了真正的问题。

前缀：
ab -> xy 和 xyc -> 123 的情况给我们带来了一个问题，即两个规则不是问题，除非给定的字符串是以某种方式构建的。（abc 变为 xyc）。这可以用以某种方式标记的有向边来检查。如果他们创建一个循环，那么您将遇到某些字符串的问题，但其他字符串不会。

希望对您有所帮助。

Repeated search replace until convergence