2

次の問題を解決するアルゴリズムを探しています。

からまでのn数字を含む数列と他の数列が与えられた場合、に等しい最小の (最小量を含む) 数列を見つけます。09mn

例

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

今まで思ったこと

FSM またはトライ木を使用して、最初に適合する最長のシーケンスを見つける基本的な貪欲な手法:

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

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 に答える