如何定义普通马尔可夫算法（NMA）来交换由符号“^”分隔的两个三进制数？

Question

我正在尝试在模拟器中编写一个普通的马尔可夫算法来交换由符号“^”分隔的两个三进制数。例如，输入“120^210”，结果应为“210^120”。

我已经尝试过这些规则：

^0 -> 0@^
^1 -> 1@^
^2 -> 2@^
@^0 -> 0@^
@^1 -> 1@^
@^2 -> 2@^
@^ -> ^
^->@
@0 -> ^0
@1 -> ^1
@2 -> ^2
@ -> ^

但它无法正常工作；我刚刚得到“120210^”。

Answer 1

当

^

符号移至最右侧并替换为

@

时，则不再适用任何规则。例如，

@0

、

@1

、

@2

永远不会发生，因此相应的规则永远不会激活，因此

@

被替换回

^

而没有完成任何事情。

我建议将任务分为以下几个阶段：

1. 将所有右侧数字转换为字母（a、b 和 c）
2. 将所有字母移至所有（剩余）数字的左侧
3. 将字母变回数字

您可以为每个阶段使用不同的标记来了解“您在哪里”。

这里是马尔可夫算法的 JavaScript 可能实现，给出了一组应用上述阶段的规则：

// Every rule consists of 3 parts: find, replace, is-terminating-rule
const rules = [
    // Map the right-side digits to letters
    ["^0", "a^", false],
    ["^1", "b^", false],
    ["^2", "c^", false],
    ["^",  "@",  false], // Mapping completed, go to next phase:
    // Move letters left of all digits
    ["0a", "a0", false],
    ["0b", "b0", false],
    ["0c", "c0", false],
    ["0@", "@0", false],
    ["1a", "a1", false],
    ["1b", "b1", false],
    ["1c", "c1", false],
    ["1@", "@1", false],
    ["2a", "a2", false],
    ["2b", "b2", false],
    ["2c", "c2", false],
    ["2@", "@2", false],
    ["@",  "<|", false], // Move completed, go to next phase:
    // Change letters back to digits
    ["a<", "<0", false],
    ["b<", "<1", false],
    ["c<", "<2", false],
    ["<",  "",   false], // Change back completed, go to last phase:
    // Terminating rule
    ["|",  "^",  true],
];

const result = applyRules("210^120", rules);
console.log("final:", result);

// Used Markov algorithm
function applyRules(str, rules) {
    for (let i = 0; i < 5000; i++) { // Avoid infinite loop
        const rule = rules.find(([find]) => str.includes(find)); 
        if (!rule) return str;
        const [find, replace, terminating] = rule;
        str = str.replace(find, replace);
        console.log(`apply rule "${find}"=>"${replace}", result="${str}"`);
        if (terminating) return str;
    }
}