Получить список наборов, где сумма каждого набора равна X

Question

Я пытаюсь выяснить, как сгенерировать список множеств, где каждый набор имеет длину N, а сумма каждого набора равна 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. 

Любые указатели?

Answer 1

Если у вас есть доступ к 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. 

Answer 2

Обеспечьте ограничение «равное или большее» между последовательными значениями в массиве.

Вы можете добавить его в качестве другого предиката:

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. 

Я не уверен, насколько больше производительности это становится, так как сравнение должно быть после рекурсии, из-за менее чем или равна оператора (= <) требует как операнды полностью создаваться для него t o работа.