序言：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

回答

相關問題