獲取每個集合的總和爲X的集合列表

我想弄清楚如何生成集合列表，其中每個集合的長度爲N，每個集合的總和爲X.獲取每個集合的總和爲X的集合列表

我發現這個代碼：

num_split(0,[]). 
num_split(N, [X | List]):- 
    between(1,N,X), 
    plus(X,Y,N), 
    num_split(Y,List).

而且我可以用它來獲得的集列表與和X：

num_split(6,List),length(List,5). 
List = [1, 1, 1, 1, 2] ; 
List = [1, 1, 1, 2, 1] ; 
List = [1, 1, 2, 1, 1] ; 
List = [1, 2, 1, 1, 1] ; 
List = [2, 1, 1, 1, 1] ; 
false.

的問題是，這些都是所有排列，和我在尋找組合。我在尋找的輸出應該是這樣的get_combos(Sum,Length,List)：

get_combos(6,2,List). 
List = [5,1]; 
List = [4,2]; 
List = [3,3]; 
false.

任何指針？

來源

2012-05-16 Sean Hagen

如果你有機會到CLP(FD)庫，你可以使用此代碼：

:- [library(clpfd)]. 

get_combos(Sum, Length, List) :- 
    length(List, Length), 
    List ins 1 .. Sum, 
% all_distinct(List), not really useful here 
    sum(List, #=, Sum), 
    chain(List, #<), 
    label(List).

測試：

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

也許我誤解你的問題。使用此鏈

... 
chain(List, #=<), 
....

獲得可能的重複值：

?- get_combos(10,3,L). 
L = [1, 1, 8] ; 
L = [1, 2, 7] ; 
L = [1, 3, 6] ; 
L = [1, 4, 5] ; 
L = [2, 2, 6] ; 
L = [2, 3, 5] ; 
L = [2, 4, 4] ; 
L = [3, 3, 4] ; 
false.

來源

2012-05-16 07:04:58 CapelliC

完美！我刪除了「鏈（List，＃<）」，因爲我正在查找所有加總爲Sum的列表，而不僅僅是有序列表。我使用代碼解決了DropQuest 2012的第1章：https://github.com/seanhagen/DropQuest-2012-Chapter-1-Prolog-Solver –

在數組中的連續值之間強制實施「等於或大於」限制。

您可以將其添加爲另一個謂詞：

is_combination([]). 
is_combination([_]). 
is_combination([A,B|List]) :- A =< B, is_combination([B|List]). 

get_combos(Sum, Length, List) :- 
    num_split(Sum, Length, List), 
    is_combination(List).

不幸的是，套結它的num_split月底/ 3不一定會增加它的性能，所以直接將其添加到算法會略好：

get_combos(_, 0, []). 
get_combos(Sum, 1, [Sum]). 
get_combos(Sum, Length, [A, B|List]) :- 
    between(1, Sum, A), 
    plus(A, NextSum, Sum), 
    plus(1, NextLength, Length), 
    get_combos(NextSum, NextLength, [B|List]), 
    A =< B.

我不知道到底有多少，更多的表現這得到，作爲比較必須是遞歸後，由於低於或-等於運算符（= <）需要同時操作數爲它完全實例化工作。

來源

2012-05-16 03:41:55 Raceimaztion

獲取每個集合的總和爲X的集合列表

回答

相關問題