获取每个集合的总和为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的集合列表

回答

相关问题