こんなプログラムを作ったけど

こないだの問題。
http://d.hatena.ne.jp/nowokay/20080717

Javaで書くとこんな感じか。

public class SBH {
    public static void main(String[] args){
        sbh(new String[]{"BAB", "ABA", "AAB", "AAA", "BAA"});
        sbh(new String[]{"BAB", "AAB", "AAA", "BAA"});
        sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "BCA", "CAB"});
        sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "CAB"});
        sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "CAB", "CAB", "BBC"});
    }
    
    public static void sbh(String[] strs){
        System.out.print("{");
        List words = new ArrayList();
        for(String str : strs) words.add(str);

        for(String start : strs){
            List wordscpy = new LinkedList(words);
            wordscpy.remove(start);
            sbh_impl(start, wordscpy);
        }
        System.out.print("}");
    }

    private static void sbh_impl(String str, List<String> words){
        if(words.size() == 0){
            //答えがでてる
            System.out.print(str + " ");
            return;
        }
        for(String s : words){
            if(!str.substring(str.length() - s.length() +1).equals(
                    s.substring(0, s.length() - 1))) continue;
            List wordscpy = new LinkedList(words);
            wordscpy.remove(s);
            sbh_impl(str + s.substring(s.length() - 1), wordscpy);
        }
    }
}

これで、こんな感じになる。

{BABAAAB BAAABAB }
{}
{CAABABCAB CAABCABAB CABABCAAB CABCAABAB }
{}
{}

ようするに、連結できるすべての組み合わせを見て、最後までたどり着けたら結果として出力。
permutationって、リストのすべての順列を求めるような関数がある環境の人は、それを使ってできたリストの連結性を検査して、全部つながったらOKみたいな感じでやってますね。

これを線形時間で解くには

さて、これで求めたい文字列が得られたわけですが、ここでアルゴリズムとして全ての順列について検査しているので、計算時間がO(n!)になってしまいます。
そこで、これを線形時間、つまり、入力文字列数nと出力文字列数mに比例した計算時間O(mn)になるようにしたい。

ということで、与えられた文字列
{"CAA", "AAB", "ABA", "BAB", "ABC", "BCA", "CAB"}
から、次のような、k-1文字の部分文字列の遷移を書いてみます。

そうすると、答えになるのは、このグラフが一筆書きできるもの、つまりオイラーパスを求めればいいということになります。そうなると、あとは一般的なグラフの問題として解くことができます。

で、この問題っていったいなんだったのかというと、バイオインフォマティクスでDNAの配列を決めるための問題で、Sequence By Hybridization(SBH)といいます。
実際のところ、測定誤差があることから、このアルゴリズムはそのままでは使いものにならないようですが、まあ、こんな考え方がベースになっているということです。

実際組もうと思ったのだけど、全ての組み合わせを線形時間で求めようとしたらめんどくさかったので、答えを一組だすものを作ってみました。

public class SBH {
    public static void main(String[] args){
        System.out.println(sbh(new String[]{"BAB", "ABA", "AAB", "AAA", "BAA"}));
        System.out.println(sbh(new String[]{"BAB", "AAB", "AAA", "BAA"}));
        System.out.println(sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "BCA", "CAB"}));
        System.out.println(sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "CAB"}));
        System.out.println(sbh(new String[]{"CAA", "AAB", "ABA", "BAB", "ABC", "CAB", "CAB", "BBC"}));
    }
    
    public static String sbh(String[] s){
        String result = "";
        if(s == null || s.length == 0) return result;
        //出る側のmatrix
        Map<String, Set<String>> matrix = new HashMap<String, Set<String>>();
        //入る側のmatrix
        Map<String, Set<String>> invmatrix = new HashMap<String, Set<String>>();
        //出入りグラフの行列を作成
        for(String str : s){
            String from = str.substring(0, str.length() - 1);
            String to = str.substring(1);
            if(!matrix.containsKey(from)) matrix.put(from, new HashSet<String>());
            matrix.get(from).add(to);
            if(!invmatrix.containsKey(from)) invmatrix.put(from, new HashSet<String>());
            if(!invmatrix.containsKey(to)) invmatrix.put(to, new HashSet<String>());
            invmatrix.get(to).add(from);
        }
        //オイラーグラフ(一筆書きできる)かどうか判定
        String outover = null;//出が超過してる
        String inover = null;//入りが超過してる
        for(String key : invmatrix.keySet()){
            int outcount = matrix.containsKey(key) ? matrix.get(key).size() : 0;
            int incount = invmatrix.get(key).size();

            if(outcount == incount){
                //出入りが同じ数
            }else if(outcount == incount + 1){
                if(outover != null){
                    //出 > 入が2つ以上あるとオイラーグラフではない
                    return result;
                }
                outover = key;
            }else if(outcount + 1 == incount){
                if(inover != null){
                    //出 > 入が2つ以上あるとオイラーグラフではない
                    return result;
                }
                inover = key;
            }else{
                //出と入の差が2以上あるとオイラーグラフではない
                return result;
            }
        }
        if((outover != null) != (inover != null)) return result;
        
        //オイラーパスを探索
        List<String> results = new LinkedList<String>();//結果
        List<String> temp = new LinkedList<String>();
        //出が多いところがあれば、そこから。そうでなければ閉路なのでどこからでもいい
        String word = (outover != null) ? outover : matrix.keySet().iterator().next();
        result += word.charAt(0);
        int insertindex = 0;
        while(matrix.size() > 0){
            temp.add(word);
            
            if(!matrix.containsKey(word)){
                //次がないばあいは、適当なところから始めて連結させる
                results.addAll(insertindex, temp);//厳密に線形にするときは、ここを工夫
                temp.clear();
                String next = matrix.keySet().iterator().next();
                insertindex = results.indexOf(word);//厳密に線形にするときは、ここを工夫
                word = next;
                continue;
            }
            
            String next = matrix.get(word).iterator().next();
            matrix.get(word).remove(next);
            if(matrix.get(word).isEmpty()) matrix.remove(word);
            word = next;
        }
        temp.add(word);
        results.addAll(insertindex, temp);
        //答えを作成
        for(String str : results) result += str.charAt(1);
        return result;
    }
    
}