% FILE: combinatorial_sets.pro
% TYPE: Prolog source
% LINE: a bit of combinatorial set code

%-----------------------------------------------------------------------------------
% perm(S,P) can be used to generate all permutations P on a set of symbols S. The 
% permutations are represented by a term beginning with small 'p' and the sets are
% represented by a term beginning with small 's'. The program for a set of n 
% elements makes use of the program for a set of n-1 elements, provided n > 2. 
% This program operates on sets of 2, 3, 4, or 5 elements only.

perm(s(A,B),p(A,B)).
perm(s(A,B),p(B,A)).

perm(s(A,B,C),p(A,X,Y)) :- perm(s(B,C),p(X,Y)).
perm(s(A,B,C),p(B,X,Y)) :- perm(s(A,C),p(X,Y)).
perm(s(A,B,C),p(C,X,Y)) :- perm(s(A,B),p(X,Y)).

perm(s(A,B,C,D),p(A,X,Y,Z)) :- perm(s(B,C,D),p(X,Y,Z)).
perm(s(A,B,C,D),p(B,X,Y,Z)) :- perm(s(A,C,D),p(X,Y,Z)).
perm(s(A,B,C,D),p(C,X,Y,Z)) :- perm(s(A,B,D),p(X,Y,Z)).
perm(s(A,B,C,D),p(D,X,Y,Z)) :- perm(s(A,B,C),p(X,Y,Z)).

perm(s(A,B,C,D,E),p(A,X,Y,Z,W)) :- perm(s(B,C,D,E),p(X,Y,Z,W)).
perm(s(A,B,C,D,E),p(B,X,Y,Z,W)) :- perm(s(A,C,D,E),p(X,Y,Z,W)).
perm(s(A,B,C,D,E),p(C,X,Y,Z,W)) :- perm(s(B,A,D,E),p(X,Y,Z,W)).
perm(s(A,B,C,D,E),p(D,X,Y,Z,W)) :- perm(s(B,C,A,E),p(X,Y,Z,W)).
perm(s(A,B,C,D,E),p(E,X,Y,Z,W)) :- perm(s(B,C,D,A),p(X,Y,Z,W)).

permutations(A,B) :- 
perm(s(A,B),p(V,W)),
write(V), write(W), write(' '),
fail.
permutations(_,_).

permutations(A,B,C) :- 
perm(s(A,B,C),p(V,W,X)),
write(V), write(W), write(X), write(' '),
fail.
permutations(_,_,_).

permutations(A,B,C,D) :- 
perm(s(A,B,C,D),p(V,W,X,Y)),
write(V), write(W), write(X), write(Y), write(' '),
fail.
permutations(_,_,_,_).

permutations(A,B,C,D,E) :- 
perm(s(A,B,C,D,E),p(V,W,X,Y,Z)),
write(V), write(W), write(X), write(Y), write(Z), write(' '),
fail.
permutations(_,_,_,_,_).

%-----------------------------------------------------------------------------------
% combo(S,C,E) can be used to generate all combinations C of size 2 on a set S of 
% elements, and additionally stores the extras E of the set that are not part
% of the combination. The sets, the combinations, and the extras are represented
% using metaknowledge in the form of simple term names (i.e., set, comb, extras).
% This program operates on sets of 3, 4, or 5 elements only.

comb(set(N1,N2,N3),comb(N1,N2),extras(N3)).
comb(set(N1,N2,N3),comb(N1,N3),extras(N2)).
comb(set(N1,N2,N3),comb(N2,N3),extras(N1)).

comb(set(N1,N2,N3,N4),comb(N1,N2),extras(N3,N4)).
comb(set(N1,N2,N3,N4),comb(N1,N3),extras(N2,N4)).
comb(set(N1,N2,N3,N4),comb(N1,N4),extras(N2,N3)).
comb(set(N1,N2,N3,N4),comb(N2,N3),extras(N1,N4)).
comb(set(N1,N2,N3,N4),comb(N2,N4),extras(N1,N3)).
comb(set(N1,N2,N3,N4),comb(N3,N4),extras(N1,N2)).

comb(set(N1,N2,N3,N4,N5),comb(N1,N2),extras(N3,N4,N5)).
comb(set(N1,N2,N3,N4,N5),comb(N1,N3),extras(N2,N4,N5)).
comb(set(N1,N2,N3,N4,N5),comb(N1,N4),extras(N2,N3,N5)).
comb(set(N1,N2,N3,N4,N5),comb(N1,N5),extras(N2,N3,N4)).
comb(set(N1,N2,N3,N4,N5),comb(N2,N3),extras(N1,N4,N5)).
comb(set(N1,N2,N3,N4,N5),comb(N2,N4),extras(N1,N3,N5)).
comb(set(N1,N2,N3,N4,N5),comb(N2,N5),extras(N1,N3,N4)).
comb(set(N1,N2,N3,N4,N5),comb(N3,N4),extras(N1,N2,N5)).
comb(set(N1,N2,N3,N4,N5),comb(N3,N5),extras(N1,N2,N4)).
comb(set(N1,N2,N3,N4,N5),comb(N4,N5),extras(N1,N2,N3)).

combinations(A,B,C) :-
comb(set(A,B,C),comb(X,Y),extras(_)),
write(X),write(Y),write(' '),
fail.
combinations(_,_,_).

combinations(A,B,C,D) :-
comb(set(A,B,C,D),comb(X,Y),extras(_)),
write(X),write(Y),write(' '),
fail.
combinations(_,_,_,_).

combinations(A,B,C,D,E) :-
comb(set(A,B,C,D,E),comb(X,Y),extras(_)),
write(X),write(Y),write(' '),
fail.
combinations(_,_,_,_,_).