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

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

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


prolog clpfd
person Sean Hagen    schedule 16.05.2012    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Если у вас есть доступ к 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.
person CapelliC    schedule 16.05.2012
comment
Идеальный! Я удалил цепочку (Список, #‹), потому что я искал все списки, которые составляют сумму, а не только упорядоченные списки. Я использовал код для решения главы 1 для DropQuest 2012: github.com/ seanhagen/DropQuest-2012-Chapter-1-Prolog-Solver - person Sean Hagen; 17.05.2012

arrow_upward
1
arrow_downward

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

Вы можете добавить его как еще один предикат:

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.

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

person Raceimaztion    schedule 16.05.2012