% FILE: combinatorial_sets.pro
% TYPE: Prolog soource
% LINE: a bit of combinatorial set code
% DATE: November, 1995 - later revised (copy date: October 2019)

%-----------------------------------------------------------------
% 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(_,_,_,_,_).