このディレクトリの索引

:- dynamic(cut,0).

最長共通部分列(_ならび1,_ならび2,_最長共通部分ならび) :-
        abolish(cut/0),
        findmin(_要素数,(
                    member(L,[_ならび1,_ならび2]),
                    length(L,_要素数)),
               _短い方のならびの要素数),
        最長共通部分列(_短い方のならびの要素数,_ならび1,_ならび2,_最長共通部分ならび).

最長共通部分列(_短い方のならびの要素数,_ならび1,_ならび2,_最長共通部分ならび) :-
        for(_短い方のならびの要素数,N,1),
        (   cut,!,fail;
            共通部分列(N,_ならび1,_ならび2,_最長共通部分ならび)
        ),
        cut_assert.

cut_assert :-
        cut,!.
cut_assert :-
        asserta(cut).

共通部分列(N,_ならび1,_ならび2,_共通部分ならび) :-
        組合せ(_ならび1,N,_共通部分ならび),
        組合せ(_ならび2,N,_共通部分ならび).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

findmin(V,P,Min) :-
        findall(V,P,L),
        min(L,Min).

組合せ(X,1,[A]) :-
        member(A,X).
組合せ([A|Y],N,[A|X]) :-
        N > 1,
        M is N - 1,
        組合せ(Y,M,X).
組合せ([_|Y],N,A) :-
        N > 1,
        組合せ(Y,N,A).