Как создать список номеров, которые складываются в определенный номер

Question

Мне нужна помощь в написании предиката в Прологе, который, учитывая число в качестве входных данных, возвращает список списков с добавляемыми к нему числами.

Давайте назовем предикат addUpList / 2 , это должно работать так:

?- addUpList(3,P).
P = [[1,2], [2,1], [1,1,1]].       % expected result

Мне так трудно понять это, я начинаю думать, что это невозможно.Есть идеи?Заранее спасибо.

Answer 1

Попробуйте:

condense([], Rs, Rs).
condense([X|Xs], Ys, Zs) :-
    condense(Xs, [X|Ys], Zs).
condense([X, Y|Xs], Ys, Zs) :-
    Z is X + Y,
    condense([Z|Xs], Ys, Zs).

condense(Xs, Rs) :-
    condense(Xs, [], Rs).

expand(0, []).
expand(N, [1|Ns]) :-
    N > 0,
    N1 is N - 1,
    expand(N1, Ns).

addUpList(N, Zs) :-
    expand(N, Xs),
    findall(Ys, condense(Xs, Ys), Zs).

Дайте мне знать, какие оценки я получаю.: -)

Answer 2

Правило num_split/2 генерирует способы разбиения числа на список, где первый элемент X - это любое число от 1 до N, а остальная часть списка - это разбиение N-X.

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

Чтобы получить все такие сплиты, просто позвоните findall/3 на num_split/2.

add_up_list(N, Splits) :-
    findall(Split, num_split(N, Split), Splits).

Пример использования:

?- add_up_list(4, Splits).
Splits =
   [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]].

См. Такжепост @hardmath, который дает тот же ответ с чуть более подробным объяснением.

Answer 3

Этот ответ находится где-то между @ ответом Каарела и "эффективным" ответом Шарки .

Как и код @ sharky, мы навязываемпорядок упорядочения между смежными элементами списка, чтобы ограничить размер пространства решения - зная, как его раздувать, если нам когда-нибудь понадобится.Таким образом, наборы решений break_down/2 и gen/2 от @sharky равны (не обращая внимания на обращение к списку).

А что касается производительности, рассмотрим:

?- time((<b>break_down</b>(<b>40</b>,_),false)).
% 861,232 inferences, 0.066 CPU in <b>0.066</b> seconds (100% CPU, 13127147 Lips)
false.

?- time((<b>gen</b>(<b>40</b>,_),false)).
% 8,580,839 inferences, 0.842 CPU in <b>0.842</b> seconds (100% CPU, 10185807 Lips)
false.

Answer 4

На этот вопрос уже есть много отличных ответов, но вот еще одно решение этой проблемы, которое вы должны рассмотреть. Эта программа отличается от других тем, что она очень эффективна и генерирует не избыточные решения списков, которые, как предполагается, представляют наборы целых чисел, которые складываются в указанное число.

gen(N, L) :-
    gen(N-1, N, N, FL),
    dup_n(FL, L).
gen(C-F, M, M, [C-F]).
gen(C-F, S, M, [C-F|R]) :-
    S < M, C > 1,
    C0 is C - 1,
    F0 is floor(M / C0),
    S0 is S + (C0 * F0),
    gen(C0-F0, S0, M, R).
gen(C-F, S, M, R) :-
    F > 0,
    F0 is F - 1,
    S0 is S - C,
    gen(C-F0, S0, M, R).

dup_n([], []).
dup_n([_-0|R], L) :-
    !, dup_n(R, L).
dup_n([V-F|R], [V|L]) :-
    F0 is F - 1,
    dup_n([V-F0|R], L).

Ваша реализация addUpList/2 может быть достигнута:

addUpList(N, P) :-
    findall(L, gen(N, L), P).

Что должно дать вам следующее поведение:

?- addUpList(4,L).
L = [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]].

Обратите внимание, что список, содержащий один 2 и два 1 с, появляется только один раз в этом наборе результатов; это потому, что gen/4 вычисляет уникальные наборы целых чисел, которые складываются в указанное число.

Answer 5

Пример, приведенный в Вопросе, предполагает, что нужны композиции (упорядоченные разбиения) любого положительного целого числа N ≤ 10.Отметим, однако, что решение [3] для N = 3, похоже, было пропущено / упущено. количество композиций для N равно 2 ^ (N-1), поэтому N = 10 дает длинный список, но не неуправляемый.

Также желательно собрать все такие решенияв список, то, что findall/3 может сделать в общем случае после того, как мы напишем предикат composition/2, который их генерирует.

Идея состоит в том, чтобы выбрать первое слагаемое, любое от 1 до N, вычесть его из общей суммы и рекурсировать (остановка с пустым списком, когда общая сумма достигает нуля).SWI-Prolog предоставляет предикат between/3, который может генерировать эти возможные первые слагаемые, и Amzi!Пролог предоставляет аналогичный предикат for/4.Ради переносимости мы напишем здесь свою собственную версию.

summand(Low,High,_) :-
    Low > High,
    !,
    fail.
summand(Low,High,Low).
summand(Low,High,Val) :-
    Now is Low + 1,
    summand(Now,High,Val).

composition(0,[ ]).
composition(N,[H|T]) :-
    summand(1,N,H),
    M is N - H,
    composition(M,T).

Учитывая приведенный выше исходный код Prolog, скомпилированный или интерпретированный, список всех решений можно получить следующим образом:

?- findall(C,composition(3,C),L).

C = H126
L = [[1, 1, 1], [1, 2], [2, 1], [3]] 

Конечно, для вашего конкретного приложения может потребоваться некоторая организация такого списка решений или пропуск одноэлементного списка, но это не ясно, поскольку Вопрос в настоящее время сформулирован.