3

Given the four digit number 1234, there are six possible two digit subsequences (12, 13, 14, 23, 24, 34). Given some of the subsequences, is it possible to recover the original number?

Here's some example data. Each line lists some 3 digit subsequences of a different 6 digit number (to be found)

528, 508, 028, 502, 058, 528, 028, 528, 552, 050
163, 635, 635, 130, 163, 633, 130, 330, 635, 135
445, 444, 444, 444, 454, 444, 445, 
011, 350, 601, 651, 601, 511, 511, 360, 601, 351
102, 021, 102, 221, 102, 100, 002, 021, 021, 121
332, 111, 313, 311, 132, 113, 132, 111, 112
362, 650, 230, 172, 120, 165, 372, 202, 702
103, 038, 138, 150, 110, 518, 510, 538, 108
343, 231, 431, 341, 203, 203, 401, 303, 031, 233

Edit: Sometimes the solution might not be unique (more than one number could have given the subsequences). In that case, it would be good to return one of them, or maybe even a list.

4

3 回答 3

3

构建一个有向图，每个数字都连接到每个序列中的数字。

处理循环：

一个循环意味着一个不可能的场景——同一个角色不能有两个位置（在多个位置可以有相同值的角色，但不是完全相同的角色——作为一个比喻，你可以有很多人叫 Bob，但是任何给定的 Bob只能在一个地方）。必须将某个节点拆分为多个节点。选择的节点应该被拆分，使得所有传入边都在新节点之一中，所有传出边都在另一个新节点中，并且两者之间存在连接。

应该有多个节点可以选择进行拆分，可能只有一个是正确的，您可能需要探索所有可能性，直到找到一个可行的。如果一个不工作，你会得到一个比某处允许的更长的字符串。

在拓扑排序之前完全摆脱循环可能是一个更好的主意（以相同的方式解决它们）。

处理具有相同值的节点（作为循环解析的结果）：

如果可以选择多个具有相同值的节点，则让出边从第一个（具有到所有其他节点的有向路径的那个）和输入边到最后一个（所有其他有一个指向的路径）。如果在同一序列中有多个具有相同值的数字，这显然需要稍微修改。

查找实际字符串：

要确定字符串，请对图进行拓扑排序。

例子：

假设我们正在寻找一个 5 位数字，输入是：

528, 508, 028, 502, 058, 058

我知道重复的058有点微不足道，但这只是为了说明。

对于, 为,和, 和连接和和,528创建节点。5285228

5 -> 2 -> 8

对于508、 创建0、 连接5和0和0和8。

5 -> 2 -> 8
  \    /
   > 0

对于028，连接0和2。

5 ------> 2 -> 8
  \    /    /
   > 0 -----

对于502，所有连接都已经存在。

对于058，我们得到一个循环 ( 5->0->5)，所以我们有 2 个选择：

  • 分成02个节点：

      /-----------\----\
 /             v    v
0 -> 5 ------> 2 -> 8
       \
        > 0

  • 分成52个节点：

      /-----------\
 /             v
5 ------> 2 -> 5 -> 8
 \        ^    ^
  \       /    /
   > 0 --------

假设我们选择后者。

对于058，我们需要从最后一个5（在本例中为右侧）的出边和来自第一个（在本例中为左侧5）的入边。这些边 (和) 已经存在，所以没有什么可做的。555->05->8

拓扑排序将给我们50258，这是我们的数字。

于 2013-08-13T14:15:38.823 回答
3

您要做的是找到所有子序列中最短的公共超序列。显然，如果您拥有所有子序列，包括原始编号，那么 SCS 将是您正在寻找的。否则不能保证，但有很好的机会。

不幸的是，对于这个问题没有一个很好的多项式算法，但如果你用谷歌搜索，你会发现有很多可用的近似算法。例如，最短公共超序列问题的 ACO 算法，其中提到了三种总体方法：

  1. 动态规划或分支'n'Bound。除了很少的字符串或小字母之外，这些通常会变慢。

  2. 使用动态编程成对查找字符串的 SCS，使用启发式方法选择要“合并”的字符串。

  3. 多数合并启发式可能是您的案例中最好的启发式。

  4. 论文中描述的方法。

这是关于这个问题的另一篇不错的文章：http ://www.update.uu.se/~shikaree/Westling/

于 2013-08-13T14:04:49.550 回答
2

让逻辑编程为您完成工作。

这是通过core.logic实现的。

定义成为子序列的含义

(defne subseqo [s1 s2] 
  ([(h . t1) (h . t2)] (subseqo t1 t2)) 
  ([(h1 . t1) (h2 . t2)] (!= h1 h2) (subseqo s1 t2)) 
  ([() _]))

通过求解器运行约束。

(defn recover6 [input-string] 
  (run* [q] 
    (fresh [a b c d e f] 
      (== q [a b c d e f]) 
      (everyg (fn [s] (subseqo (seq s) q)) 
              (re-seq #"\d+" input-string)))))

示例（结果在 REPL 上是即时的）：

(recover6 "528, 508, 028, 502, 058, 528, 028, 528, 552, 050")
;=> ([\5 \0 \5 \2 \8 \0]
     [\5 \0 \5 \2 \0 \8]
     [\5 \0 \5 \0 \2 \8]
     [\0 \5 \0 \5 \2 \8]
     [\0 \5 \5 \0 \2 \8])

(recover6 "163, 635, 635, 130, 163, 633, 130, 330, 635, 135")
;=> ([\1 \6 \3 \5 \3 \0] 
     [\1 \6 \3 \3 \5 \0] 
     [\1 \6 \3 \3 \0 \5])

(recover6 "445, 444, 444, 444, 454, 444, 445")
;=> ([\4 \4 \5 \4 _0 _1] 
     ... and many more

在最后一个示例中，下划线表示_0和_1是自由变量。他们没有受到限制。将任何自由变量约束到一组数字是很容易的。

于 2013-08-13T18:11:29.497 回答