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]]

len([], 0). len([H|T], result) :- len(T, L), result is L + 1. This is what I came up with to calculate list's length which is needed if I were to use 2nd kind stirling number. As for the sets I've been experimenting, but nothing conclusive. My biggest issue is how I can make a number of resulting subsets decided by a variable not a number of variables. — Please be gentle, Jan 11 '18 at 19:03
So basicaly you have a list of n elements and you want to have a list with n sublist of m elements. So for instance for A = [1,2,3,4] to B = [[1,2],[3,4]] right? — damianodamiano, Jan 11 '18 at 19:06
let's say my input is a list = [1,2,3] and m = 2 then the result should be 1. [[1], [2, 3]] 2. [[2], [1, 3]] 3. [[3], [1, 2]], only input list and the number of sublists is a variable, number of elements in each sublist is >=1 — Please be gentle, Jan 11 '18 at 19:14
Look at this https://stackoverflow.com/questions/4912869/subsets-in-prolog — damianodamiano, Jan 11 '18 at 19:16
If you want to show the code you tried, please edit your question and include it there, properly formatted. Don't put it in comments. It's not very readable there, and isn't readily visible to those who see your question. — lurker, Jan 11 '18 at 19:50
@damianodamiano I have checked that topic, unfortunately only a bare solution with no explanation is given and thus I am not able to understand it or apply to my problem. lurker The piece of code I have written is only "a side problem" to the whole problem which I'm not even sure is necessary so I didn't think I should include it in the topic. — Please be gentle, Jan 11 '18 at 21:29
@lurker I have reedited my problem to make it a lot more readable and understandable, could you have a look please? — Please be gentle, Jan 12 '18 at 14:52

repeat · Accepted Answer · 2018-01-16T00:00:45.163

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

Of interest: [Termination](https://www.metalevel.at/prolog/termination) — Guy Coder, Jan 30 '19 at 19:50
@GuyCoder. Your eyes are very sharp:) The implementation constrains all parts to be non-empty to give the predicate good universal termination properties. If you need the corner case defined differently, that can be done with an extra predicate. — repeat, Jan 30 '19 at 23:24
@GuyCoder. The "NU"-predicate has a simple idea: use additional constraints to limit the search space. — repeat, Jan 30 '19 at 23:36
@GuyCoder. Does the list that you want to partition contain any duplicates elements? Duplicate items can lead to a considerable number of redundant answers. Eliminating these redundant answers has costs, but can reduce runtime. YMMV! — repeat, Jan 31 '19 at 09:46

lurker · Answer 2 · 2018-01-13T14:54:06.907

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.

thank you very much, I've been analyzing "all partitions of a list" for more than 5 hours now, but just couldn't translate it into my problem, seems like a very limited knowledge of prolog and its quirks is my problem, also do you think there would be a "cleaner" solution than filtering all possible partitions? — Please be gentle, Jan 12 '18 at 16:01
@Pleasebegentle if you find the above answer acceptable, I'd appreciate if you could accept it. See my updated answer and concluding comments there. — lurker, Jan 12 '18 at 21:59
What `library(statistics)` are you using? In SICStus there is a module with that name, but it implements predicates about averages, medians and kurtosis. — repeat, Jan 13 '18 at 09:00

partition a set into n subsets using prolog

2 Answers2

Linked