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

こないだの問題。
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みたいな感じでやってますね。