序言：k元素与元素总和的排列S

我想要计算在Prolog中K元素的排列，其中元素的总和等于给定的S。所以，我知道可以通过找到组合来计算排列，然后对它们进行排列。我知道如何计算K要素的组合，是这样的：序言：k元素与元素总和的排列S

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元素的总和。任何帮助，将不胜感激。

来源

2016-02-12 Nelly

你正在使用* any *数字，还是只使用整数？ – repeat

只限于整数 – Nelly

您使用哪种Prolog处理器？ SICStus？ SWI？ – repeat

我使用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备注后编辑。

来源

2016-02-12 09:14:56 joel76

什么是'when（ground（L），...）'？哪些用例可以从中受益？ – repeat

@repeat你是绝对正确的，这是没有必要的。 – joel76

使用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：

 
?- length(Zs, 4), Zs ins 1..4, chain (Zs, #=<), sum(Zs, #=, 7), labeling([], Zs). 
    Zs = [1,1,1,4] 
; Zs = [1,1,2,3] 
; Zs = [1,2,2,2] 
; false.

来源

2016-02-12 09:54:53 repeat

我尝试做这个qst，但我有这个结果（长度= 3，Sum3）：'List = [_A，_B，_C]， _A in inf .sup， _B in inf .sup， _C in inf..sup？'我如何从'inf..sup'恢复数值 –

@AnsPiter尝试在'Sum3'中尝试提供一个值而不是变量？为了解释你的代码，你基本上是在说：“给我三件东西加起来就可以了。” CLP回来了，“这里有三件事情有什么价值。”这就是重复给出'Zs ins 1..4'和'sum（Zs，＃=，7）'来约束解空间的原因。 –

@AnsPiter。丹尼尔是对的。如果您使用SICStus，请执行'assert（clpfd：full_answer）'以确保[tag：prolog-toplevel]显示剩余约束 - 因此您不会得到印象，证明完全不是！ – repeat

此响应类似于响应@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

来源

2016-02-13 12:08:13

保持简单！使用SICStus Prolog 4.3.2，将库谓词'domain/3'和'sum/3'用得很好：长度（Zs，4），域（Zs，1,4），和（Zs，＃） =，7），标签（[]，Zs）。 – repeat

@repeat thnx，但我如何过滤重复的结果，如[0,0,0,7]和[0,7,0,0] ... ？ –

也许重复使用一些旧代码：http://stackoverflow.com/a/31094645/4609915 – repeat

我不认为排列可能与您的问题有关。由于求和操作是可交换的，所以元素的顺序实际上应该是不相关的。所以，这个修正

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把所有名单一次，如果你需要他们。

来源

2016-02-15 02:36:45 CapelliC

谢谢！这是一个好方法:-) – Nelly

序言：k元素与元素总和的排列S

回答

相关问题