partition a set into n subsets using prolog

Question

I'm struggling with the following problem, partition a set into n subsets using prolog.

So for example, I give as input to program: X = [1,2,3,4], N=3 and I get

Res = [[1,2], [3], [4]]
Res = [[1,3], [2], [4]]
Res = [[1,4], [2], [3]]
Res = [[2,3], [1], [4]]
Res = [[2,4], [1], [3]]
Res = [[3,4], [1], [2]]

or I give as input: X = [1,2,3,4], N=2 and I get

Res = [[1,2], [3,4]]
Res = [[1,3], [2,4]]
Res = [[1,4], [2,3]]
Res = [[1,2,3], [4]]
Res = [[1,2,4], [3]]
Res = [[1,3,4], [2]]
Res = [[2,3,4], [1]]

Answer 1

The problem is already mostly solved in this question: All Partitions of a List In Prolog. This was easy to find just doing a Google search on "Prolog partition set".

Then you can just constrain it with length/2:

partitions_of_length(List, N, Partition) :-
    length(Partition, N), list_partitioned(List, Partition).

| ?- partitions_of_length([a,b,c,d], 2, L).

L = [[a,b,c],[d]] ? ;

L = [[a,b,d],[c]] ? ;

L = [[a,b],[c,d]] ? ;

L = [[a,c,d],[b]] ? ;

L = [[a,c],[b,d]] ? ;

L = [[a,d],[b,c]] ? ;

L = [[a],[b,c,d]] ? ;

no
| ?-

We optimize performance in this case by constraining the length first. Below illustrates, in SWI Prolog, the difference between constraining the length after versus before:

:- use_module(library(statistics)).

6 ?- time((list_partitioned([a,b,c,d], P), length(P, 2))).
% 18 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 1580195 Lips)
P = [[a, b, c], [d]] ;
% 12 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 1059696 Lips)
P = [[a, b, d], [c]] ;
% 10 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 900414 Lips)
P = [[a, b], [c, d]] ;
% 19 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 1624070 Lips)
P = [[a, c, d], [b]] ;
% 10 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 1021555 Lips)
P = [[a, c], [b, d]] ;
% 19 inferences, 0.000 CPU in 0.000 seconds (87% CPU, 1665060 Lips)
P = [[a, d], [b, c]] ;
% 19 inferences, 0.000 CPU in 0.000 seconds (87% CPU, 1661420 Lips)
P = [[a], [b, c, d]] ;
% 37 inferences, 0.000 CPU in 0.000 seconds (90% CPU, 2382639 Lips)
false.

7 ?- time((length(P, 2), list_partitioned([a,b,c,d], P))).
% 13 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 1175832 Lips)
P = [[a, b, c], [d]] ;
% 6 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 742023 Lips)
P = [[a, b, d], [c]] ;
% 6 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 848896 Lips)
P = [[a, b], [c, d]] ;
% 9 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 1210328 Lips)
P = [[a, c, d], [b]] ;
% 6 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 828386 Lips)
P = [[a, c], [b, d]] ;
% 9 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 1215723 Lips)
P = [[a, d], [b, c]] ;
% 9 inferences, 0.000 CPU in 0.000 seconds (90% CPU, 697999 Lips)
P = [[a], [b, c, d]] ;
% 10 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 991277 Lips)
false.

If you were to modify the code in the link above to constrain the length of the list, the best way is probably to put the length/2 call inside the predicate before doing anything else, but the behavior is identical then to the above.

Answer 2

This answer extends @lurker's previous answer with additional (redundant) constraints.

Using dcg we define the following auxiliary non-terminals:

same_length([]) --> [].                         % DCG-style same_length/2
same_length([_|Es]) --> [_], same_length(Es).

same_length1([_|Es]) --> [_], same_length(Es).

same_lengths1([]) --> [].
same_lengths1([Es|Ess]) --> same_length1(Es), same_lengths1(Ess).

We utilize these DCGs by adding a phrase/2 goal upfront:

list_partitionedNU(Es, Xss) :-
   phrase(same_lengths1(Xss), Es),
   list_partitioned(Es, Xss).

Do we still get reasonable answers for some vanilla test case?

?- list_partitionedNU([a,b,c], Xss).
   Xss = [[a],[b],[c]]
;  Xss = [[a],[b,c]]
;  Xss = [[a,b],[c]]
;  Xss = [[a,c],[b]]
;  Xss = [[a,b,c]]
;  false.

Sure looks okay to me.

Next, let's talk about universal termination. Goals like list_partitioned(Es, [[a,b,c]]) do not terminate universally—even though they are trivial. list_partitionedNU/2 fixes this:

?- list_partitioned(Es, [[a,b,c]]).
   Es = [a,b,c]
;  NONTERMINATION

?- list_partitionedNU(Es, [[a,b,c]]).
   Es = [a,b,c]
;  false.                                          % terminates universally

These additional constraints can speedup some queries considerably.

Using SICStus Prolog 4.4.0:

| ?- use_module(library(between), [numlist/3]).
yes

| ?- numlist(1, 14, _Es),
     length(_Xss, 10),
     member(P_2, [list_partitioned,list_partitionedNU]),
     call_time((call(P_2,_Es,_Xss), false ; true), T_msec).
P_2 = list_partitioned  , T_msec = 29632 ? ;
P_2 = list_partitionedNU, T_msec =   600 ? ;       % 40x faster
no

Alright! Of course, the speedup depends on the actual lengths of the lists used... YMMV:)