Разбить множество на n подмножеств, используя пролог

Question

Я борюсь со следующей проблемой, разделить набор на n подмножеств, используя пролог.

Так, например, я даю в качестве входных данных для программы: X = [1,2,3,4], N=3, и я получаю

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

или я даю в качестве ввода: X = [1,2,3,4], N=2 и я получаю

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

Этот ответ расширяет предыдущий ответ @lurker дополнительными (избыточными) ограничениями.

Используя dcg, мы определяем следующие вспомогательные нетерминалы:

same_length ([]) -> [].                         % DCG-стиль 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).

Мы используем эти DCG, добавив phrase/2 цель заранее:

list_partitionedNU (Es, Xss): -
   фраза (same_lengths1(Xss), Es),
   list_partitioned(Es, Xss).

Получаем ли мы разумные ответы на какой-нибудь ванильный тест?

? - 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]]; ложный.

Конечно, выглядит хорошо для меня.

Далее поговорим об универсальном терминации. Цели как list_partitioned(Es, [[a,b,c]]) не заканчиваются универсально - даже если они тривиальны. list_partitionedNU/2 исправляет это:

? - list_partitioned (Es, [[a, b, c]]).
   Es = [a, b, c]; NONTERMINATION? - list_partitionedNU(Es, [[a, b, c]]).
   Es = [a, b, c]; ложный. % завершается повсеместно

Эти дополнительные ограничения могут значительно ускорить некоторые запросы.

Использование SICStus Prolog 4.4.0:

|? - use_module ( библиотека (между), [numlist / 3]).
да

|?- numlist(1, 14, _Es),
     длина (_Xss, 10),
     член (P_2, [list_partitioned,list_partitionedNU]),
     call_time((вызов (P_2,_Es,_Xss), false; true), T_msec).
P_2 = list_partitioned, T_msec = 29632?;
P_2 =NU с разделенным списком, T_msec =   600?;       % В 40 раз быстрее нет

Хорошо! Конечно, ускорение зависит от фактической длины используемых списков... YMMV:)

Answer 2

Проблема в основном уже решена в этом вопросе: Все разделы списка в прологе. Это было легко найти, просто выполнив поиск в Google по "набору разделов Prolog".

Тогда вы можете просто ограничить это 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
| ?-

Мы оптимизируем производительность в этом случае, сначала ограничивая длину. Ниже в SWI Prolog показано различие между ограничением длины после и до:

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

Если бы вы изменили код в приведенной выше ссылке, чтобы ограничить длину списка, лучшим способом, вероятно, было бы поставить length/2 вызовите внутри предиката, прежде чем делать что-либо еще, но поведение идентично вышеупомянутому.