prolog - 在 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

如果您的问题不需要 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).