順列 - MEMO:はてな支店

自分でチャレンジしてみたけど、書けなかったのでカンニング。

permutation(,).
permutation(Xs,[Z|Zs]) :- select(Z,Xs,Ys), permutation(Ys,Zs).

select(X,[X|Xs],Xs).
select(Y,[X|Xs],[X|Ys]) :- select(Y,Xs,Ys).
http://it.wikipedia.org/wiki/Prolog

selectはこんな感じで動く。

?- select(X,[1,2,3],Y).
X = 1,
Y = [2, 3] ;
X = 2,
Y = [1, 3] ;
X = 3,
Y = [1, 2] ;

?- select(1,X,[2,3]).
X = [1, 2, 3] ;
X = [2, 1, 3] ;
X = [2, 3, 1] ;

全てをリストで繋げて返値にするしかないlisp,haskellと違って、prologはバックトラックの先に潜在的に値を持たせる作法になるのがいいなあ。