2

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

给定n包含数字 from 0to9和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)
4

2 回答 2

2

您可以使用动态规划逐步计算结果。

让我们定义 s(i) 生成 n 的前 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)顺序计算。在每个步骤中，您都会查看从toi开始的所有序列并保持最短。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
于 2013-08-01T10:16:29.200 回答
0

基于 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]
于 2017-08-30T20:13:37.623 回答