序列覆盖算法

Question

我正在寻找一种算法来解决以下问题：

如果序列n包含从0到9的数字，以及m其他序列，则查找最小(包含最低数量)序列序列，这些序列等于n。

示例

n = 123456
m1 = 12
m2 = 34
m3 = 56
m4 = 3456
output = m1 + m4 = 123456

到目前为止我一直在想的事情，

基本贪婪技术使用FSM或trie树在开头找到适合的最长序列：

while n not null
    longest = the longest sequence fitting in the beginning of n
    print longest
    n = n - longest

反例

n = 123456
m1 = 12
m2 = 1
m3 = 23456
m4 = 3
m5 = 4
m6 = 5
m7 = 6
algorithm will find m1 + m4 + m5 + m6 + m7 (12 + 3 + 4 + 5 + 6)
algorithm should find m2 + m3 (1 + 23456)

另一种贪婪的方法

array = {n} #this represents words to be matched
while array not empty
    (word, index) = find longest sequence covering part of any word in array and its index
    split array[index] into two words - first before found word, second after it
    if any of those split items is null
        remove it

反例

n = 12345678
m1 = 3456
m2 = 1
m3 = 2
m4 = 7
m5 = 8
m6 = 123
m7 = 45
m8 = 678
algorithm will find m2 + m3 + m1 + m4 + m5 (1 + 2 + 3456 + 7 + 8)
algorithm should find m6 + m7 + m8 (123 + 45 + 678)

Answer 1

可以使用动态规划一步一步地计算结果。

让我们定义产生n的第一个i字元的最短序列s(i)。

对于上一个示例的数据，s(i)的值是：

s(0) = { }    
s(1) = { m2 }
s(2) = { m2 + m3 }
s(3) = { m6 }
s(4) = { }       (no sequence can generate "1234")
s(5) = { m6 + m7 }
s(6) = { m2 + m3 + m1 }
s(7) = { m2 + m3 + m1 + m4 }
s(8) = { m6 + m7 + m8 }

您必须按顺序计算s(1)到s(n)。在每一步i中，您都会查找从s(0)到s(i-1)的所有序列，并保持最短。

例如，对于s(8)，您发现有两个解决方案：

s(8) = s(5) + m8
s(8) = s(7) + m5

你留着最短的。

算法：

function computeBestSequence(word, list of subsequences m)

let s(0) :=  {}
for i from 1 to n     // We will compute s(i)
   let minSize := +inf.
   for j from 0 to i - 1        
      for all sequences mx from m1 to m9
         if s(j) + mx = the first i char of word
             if size of s(j) + mx is less than minSize
                minSize := size of s(j) + mx
                s(i) := s(j) + mx

编辑：

该算法可以简化为只使用两个循环：

let s(0) :=  {}
for i from 1 to n     // We will compute s(i)
   let minSize := +inf.
   for all sequences mx from m1 to m9
      let j := i - mx.length
      if s(j) + mx = the first i char of word
          if size of s(j) + mx is less than minSize
              minSize := size of s(j) + mx
              s(i) := s(j) + mx

Answer 2

基于obourgains编辑版本的java代码：

import java.util.LinkedList;
import java.util.List;

public class BestSequence {

public static List<String> match(String word, List<String> subsequences) {
    int n = word.length();

    //let s(0) :=  {}
    List<List<String>> s = new LinkedList<>();
    for(int i = 0; i <= n; i++)
        s.add(new LinkedList<>());

    //for i from 1 to n
    for(int i = 1; i <= n; i++) {
        //let minSize := +inf.
        int minSize = Integer.MAX_VALUE;

        //for all sequences mx from m1 to m9
        for(String mx : subsequences) {
            //let j := i - mx.length
            int j = i - mx.length();

            if(j < 0)
                continue;

            //if s(j) + mx = the first i char of word
            if(word.substring(0, i).equals(concat(s.get(j)) + mx)) {
                //if size of s(j) + mx is less than minSize
                if(s.get(j).size() + 1 < minSize) {
                    //minSize := size of s(j) + mx
                    minSize = s.get(j).size() + 1;
                    //s(i) := s(j) + mx
                    List<String> sj = new LinkedList<>(s.get(j));
                    sj.add(mx);
                    s.set(i, sj);
                }
            }
        }
    }
    return s.get(n);
}

private static String concat(List<String> strs) {
    String s = "";
    for(String str : strs) {
        s += str;
    }
    return s;
}

}

测试：

@Test
public void bestSequenceTest() {
    List<String> l = BestSequence.match("123456", Arrays.asList("12", "34", "56", "3456"));
    System.out.println(l);
}

产出：

[12, 3456]