list - Prolog:具有元素总和 S 的 k 个元素的排列

Question

我正在尝试计算 K 的排列Prolog 中的元素，其中元素的总和等于给定的 S .所以，我知道可以通过找到组合然后排列它们来计算排列。我知道如何计算 K 的组合元素，例如:

comb([E|_], 1, [E]).
comb([_|T], K, R) :-
   comb(T, K, R).
comb([H|T], K, [H|R]) :-
   K > 1,
   K1 is K-1,
   comb(T, K1, R).

列表的排列，具有其元素之和等于给定 S 的属性，我知道这样计算:

insert(E, L, [E|L]).
insert(E, [H|T], [H|R]) :-
   insert(E, T, R).

perm([], []).
perm([H|T], P) :-
   perm(T, R),
   insert(H, R, P).

sumList([], 0).
sumList([H], H) :-
   number(H).
sumList([H|Tail], R1) :-
   sumList(Tail, R),
   R1 is R+H.

perms(L, S, R) :-
   perm(L, R),
   sumList(R, S1),
   S = S1.

allPerms(L, LP) :-
   findall(R, perms(L,R), LP).

问题是我不知道如何组合它们，以便得到 K的安排。元素，元素的总和等于给定的 S .任何帮助，将不胜感激。

Answer 1

使用clpfd !
:- use_module (library(clpfd))。

使用 SWI-Prolog 7.3.16 我们查询:
?- length (Zs,4), Zs ins 1..4, sum (Zs,#=,7), labeling ([],Zs)。
Zs = [1,1,1,4]
; Zs = [1,1,2,3]
; Zs = [1,1,3,2]
; Zs = [1,1,4,1]
; Zs = [1,2,1,3]
; Zs = [1,2,2,2]
; Zs = [1,2,3,1]
; Zs = [1,3,1,2]
; Zs = [1,3,2,1]
; Zs = [1,4,1,1]
; Zs = [2,1,1,3]
; Zs = [2,1,2,2]
; Zs = [2,1,3,1]
; Zs = [2,2,1,2]
; Zs = [2,2,2,1]
; Zs = [2,3,1,1]
; Zs = [3,1,1,2]
; Zs = [3,1,2,1]
; Zs = [3,2,1,1]
; Zs = [4,1,1,1]。

要消除“冗余模置换”解决方案，请使用 chain/2 :
?- 长度(Zs,4), Zs ins 1..4, chain (Zs,#=<), sum(Zs,#=,7), 标签([],Zs)。
Zs = [1,1,1,4]
; Zs = [1,1,2,3]
; Zs = [1,2,2,2]
;错误的。