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]]
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:)
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.
