All partitions of a list in prolog

Question

I am coding in Prolog. I want to find all distinct partitions of a list. I look at a list as a set here. Each partition is a set of sets in which none is empty, the union of all of them is the main set, and the pairwise intersection of them is empty.

Answer 1

First, we define an auxiliary predicate list_taken_rest/3:

list_taken_rest([], [], []).
list_taken_rest([X|Xs], [X|Ys], Zs) :-
   list_taken_rest(Xs, Ys, Zs).
list_taken_rest([X|Xs], Ys, [X|Zs]) :-
   list_taken_rest(Xs, Ys, Zs).

Let's look at a query of list_taken_rest/3 with the first argument being the list [a,b,c]. As answers we get alternative ways of parting the element of [a,b,c] between Xs and Ys:

?- list_taken_rest([a,b,c], Xs, Ys).
   Xs = [a,b,c], Ys = []
;  Xs = [a,b],   Ys = [c]
;  Xs = [a,c],   Ys = [b]
;  Xs = [a],     Ys = [b,c]
;  Xs = [b,c],   Ys = [a]
;  Xs = [b],     Ys = [a,c]
;  Xs = [c],     Ys = [a,b]
;  Xs = [],      Ys = [a,b,c].

Next, we define the predicate list_partitioned/2, building on list_taken_rest/3.

As we "walk along" the list [X|Xs]:

• A single partition is [X|Ys] gets built.
• That partition contains X as the first element and some other items of Xs in Ys.
• All items in Xs that were not taken into Ys end up being in Zs.
• We proceed similarly until Xs = [] holds.

list_partitioned([], []).
list_partitioned([X|Xs], [[X|Ys]|Pss]) :-
   list_taken_rest(Xs, Ys, Zs),
   list_partitioned(Zs, Pss).

Done! Let's use list_partitioned/2 in some queries!

?- list_partitioned([1,2,3,4], Pss).          % query #1
   Pss = [[1,2,3,4]]
;  Pss = [[1,2,3],[4]]
;  Pss = [[1,2,4],[3]]
;  Pss = [[1,2],[3,4]] 
;  Pss = [[1,2],[3],[4]]
;  Pss = [[1,3,4],[2]]
;  Pss = [[1,3],[2,4]]
;  Pss = [[1,3],[2],[4]]
;  Pss = [[1,4],[2,3]]
;  Pss = [[1,4],[2],[3]]
;  Pss = [[1],[2,3,4]]
;  Pss = [[1],[2,3],[4]]
;  Pss = [[1],[2,4],[3]]
;  Pss = [[1],[2],[3,4]]
;  Pss = [[1],[2],[3],[4]].

?- list_partitioned([1,1,1], Pss).            % query #2
   Pss = [[1,1,1]]
;  Pss = [[1,1],[1]] 
;  Pss = [[1,1],[1]]                          %   (redundant answer)
;  Pss = [[1],[1,1]]
;  Pss = [[1],[1],[1]].

Note that list_partitioned/2 doesn't care about sets at all:

• If Ls is a set (like in query #1), all answers will be solutions.
• If Ls contains duplicates (like in query #2), we get some redundant answer(s).

Answer 2

part([Single], [[Single]]).

part([First|Others], [[First] | Result]) :-
    part(Others, Result).

part([First|Others], Result) :-
    part(Others, Temp),
    addElement(First, Temp, Result).

/* addElement(E, L, R) iff R is the same list of lists as L, except one of its sublist has an extra E in front */

addElement(Element, [FirstList | OtherLists], 
           [ [Element|FirstList] | OtherLists]).
addElement(Element, [FirstList | OtherLists], 
           [ FirstList | Temp] )
              :- addElement(Element, OtherLists, Temp).

Execution:

?- part([a,b,c,d],X).
X = [[a], [b], [c], [d]] ;
X = [[a], [b], [c, d]] ;
X = [[a], [b, c], [d]] ;
X = [[a], [c], [b, d]] ;
X = [[a], [b, c, d]] ;
X = [[a, b], [c], [d]] ;
X = [[b], [a, c], [d]] ;
X = [[b], [c], [a, d]] ;
X = [[a, b], [c, d]] ;
X = [[b], [a, c, d]] ;
X = [[a, b, c], [d]] ;
X = [[b, c], [a, d]] ;
X = [[a, c], [b, d]] ;
X = [[c], [a, b, d]] ;
X = [[a, b, c, d]] ;
false.