在 Prolog 中求解集合划分

Question

我正在尝试解决序言中的设置分区问题。假设，设 S = {1,3,4,2,5}。现在对其进行分区

L U R = S && L^R = empty

我想实现一个谓词 partition/3 使得 ?- partition(S,L,R) 成功当且仅当 L 和 R 是 S 的有效分区。例如， partition([1,2,3],L,R) 应该成功替换答案 L = [1,2], R = [3] 。我不想考虑这个问题的重复条目。

Answer 1

这是append/3谓词的大小写用法，我们只需要转换参数即可。

?- append(R, L, [1,2,3]).
L = [1, 2, 3],
R = [];
L = [2, 3],
R = [1];
L = [3],
R = [1, 2];
L = [],
R = [1, 2, 3];
false

这将找到列表中所有可能的有序分区，现在您需要验证其成员的总和。

现在你的谓词 partition/3 应该是这样的：

sumList([], 0).
sumList([Head|Tail], S):- number(Head), sumList(Tail, S1), S is S1 + Head.

partition(L1, L, R):- append(L, R, L1), sumList(L, S), sumList(R, S).

测试：

?- partition([1,2,3], L, R).
L = [1, 2],
R = [3]

这个答案的问题是只能找到有序的分区

Answer 2

如果您的问题不要求 sum(L) = sum(R) 通常针对 Partition Problem，那么

partition(S, [ItemL|L], [ItemR|R]):-
  partition1(S, [ItemL|L], [ItemR|R]).

partition1([], [], []).
partition1([Item|S], [Item|L], R):-
  partition1(S, L, R).
partition1([Item|S], L, [Item|R]):-
  partition1(S, L, R).

如果约束 sum(L) = sum(R) 成立，则对 partition/3 的更改将起作用（尽管效率很低）：

partition(S, [ItemL|L], [ItemR|R]):-
  partition1(S, [ItemL|L], [ItemR|R]),
  sumlist([ItemL|L], Sum),
  sumlist([ItemR|R], Sum).

在 Prolog 中求解集合划分

Solving set partition in Prolog

prolog