Prolog: k个元素的和为S的排列

Question

Prolog: k个元素的和为S的排列

5

我正在尝试在Prolog中计算K个元素的排列，其中它们的元素之和等于给定的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).

问题在于我不知道如何将它们组合起来，以得到元素总和为给定的 S 的 K 个元素的排列。感谢任何帮助。

- Nelly

你是否在使用任何数字，或者只使用整数？ - repeat

你使用的是哪个 Prolog 处理器？SICStus？SWI？ - repeat

4个回答

4

我使用SWI-Prolog。你可以写下来。

:- use_module(library(lambda)).

arrangement(K, S, L) :-
    % we have a list of K numbers
    length(L, K),
    % these numbers are between 1 (or 0) and S
    maplist(between(1, S), L),
    % the sum of these numbers is S
    foldl(\X^Y^Z^(Z is X+Y), L, 0, S).

结果

 ?- arrangement(5, 10, L).
L = [1, 1, 1, 1, 6] ;
L = [1, 1, 1, 2, 5] ;
L = [1, 1, 1, 3, 4] ;
L = [1, 1, 1, 4, 3] .

你也可以使用CLP(FD)库。

在@repeat的提醒下进行了编辑。

- joel76

when(ground(L), ...) 是什么意思？哪些使用情况可以从中受益？ - repeat

@repeat 你说得非常正确，确实没有必要这样做。 - joel76

1

这个响应与@repeat的响应类似。

下面的谓词是使用SICStus 4.3.2工具实现的。

在对gen_list(+,+,?)进行简单修改后。

编辑代码。

gen_list(Length,Sum,List) :-    length(List,Length), 
                                domain(List,0,Sum), 
                                sum(List,#=,Sum), 
                                labeling([],List),

                                % to avoid duplicate results
                                ordered(List).

测试

| ?- gen_list(4,7,L).
L = [0,0,0,7] ? ;
L = [0,0,1,6] ? ;
L = [0,0,2,5] ? ;
L = [0,0,3,4] ? ;
L = [0,1,1,5] ? ;
L = [0,1,2,4] ? ;
L = [0,1,3,3] ? ;
L = [0,2,2,3] ? ;
L = [1,1,1,4] ? ;
L = [1,1,2,3] ? ;
L = [1,2,2,2] ? ;
no

- Ans Piter

1

保持简单！使用SICStus Prolog 4.3.2，将库谓词domain/3和sum/3充分利用：?- length(Zs,4), domain(Zs,1,4), sum(Zs,#=,7), labeling([],Zs). - repeat

1

我没有理解你的意思。你说的“可能无法避免重复结果”是什么意思？你尝试过 ordered/1（上面的链接）了吗？ - repeat

1

好的！但是为什么你要写成 labeling([],List), ordered(List), Res = List ; false 而不是 ordered(List), labeling([],List) 并且在整个过程中都使用 List？一般来说，在标记之前发布约束更可取。 - repeat

1

更好了，是的。但为什么要把 labeling/2 目标放在 ordered/1 目标之前呢？这里有一些很好的材料，解释了为什么最后执行 labeling 是正确的：https://github.com/triska/clpfd/blob/master/clpfd.pdf - repeat

1

不要随便选择任何实现方式！坚持使用此答案中提供的实现方式：https://dev59.com/XknSa4cB1Zd3GeqPKxEA#31094645。 - repeat

显示剩余5条评论

0

我认为排列组合对你的问题没有什么用处。由于求和操作是可交换的，元素的顺序实际上应该是无关紧要的。所以，在进行这个修正之后

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

你可以直接使用你的谓词

'arrangements of K elements'(Elements, K, Sum, Arrangement) :-
    comb(Elements, K, Arrangement),
    sumList(Arrangement, Sum).

测试：

'arrangements of K elements'([1,2,3,4,5,6],3,11,A).
A = [2, 4, 5] ;
A = [2, 3, 6] ;
A = [1, 4, 6] ;
false.

如果你需要的话，你已经知道如何使用findall/3一次性获取所有列表。

- CapelliC

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- repeat · Accepted Answer

请使用 clpfd!

:- use_module(library(clpfd)).

使用 SWI-Prolog 7.3.16 我们查询:

?- length(Zs,4), Zs ins 1..4, sum(Zs,#=,7), labeling([],Zs).
   当Zs的长度为4时，Zs中的元素取值范围在1到4之间，
   Zs中所有元素的和等于7，使用labeling方法求解。
   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设置为1..4，chain(Zs,#=<)，将Zs的总和设置为7，利用标签求解并输出Zs的结果。
   Zs = [1,1,1,4]
;  Zs = [1,1,2,3]
;  Zs = [1,2,2,2]
;  false.