Я пытался научить себя Prolog в течение нескольких недель. Прямо сейчас я пытаюсь найти все способы сделать большое целое число из нескольких меньших целых чисел, используя предикат partition/3
, который я хочу работать так:
| ?- partition(4, [1, 2, 3], X).
X = [1, 1, 1, 1] ? ;
X = [1, 1, 2] ? ;
X = [1, 3] ? ;
X = [2, 2] ? ;
no
таким образом найти все способы сделать 4 из 1, 2 и 3. Повторяющиеся решения, такие как [1, 2, 1] и [2, 1, 1], хороши, но, вероятно, их нетрудно избежать. Вот что у меня есть прямо сейчас:
partition(N, _, []) :- N = 0.
partition(N, [], _) :- fail.
partition(N, [IH|IT], [OH|OT]) :-
N =< 0, fail;
N > IH, M is N-IH, OH = IH,
partition(M, [IH|IT], OT).
% if the first input IH can be subtracted from N,
% do so into M and push IH into the output list [OH|OT]
partition(N, [_|IT], Output) :-
N =< 0, fail;
partition(N, IT, Output).
% after trying the first input term, try the others
Идея состоит в том, что N в конечном итоге станет равным нулю, а полученные вычитания будут помещены в третий аргумент в виде списка. Третье и четвертое правила работают только с положительными целыми числами, второе правило говорит, что нельзя исчерпать входные данные, а первое правило сигнализирует, что разбиение допустимо, когда N достигает нуля. Проблема в том, что я получаю только:
| ?- partition(4, [1, 2, 3], X).
no
Первое и второе правила мне понятны, третье и четвертое кажутся сомнительными, но я не могу найти в них ничего особенно неправильного. Я думал, что выходной хвост OT
может не быть создан, когда M станет равным нулю, но первое правило позаботится об этом. Или есть какое-то фундаментальное непонимание того, как работает Пролог (что, вероятно, часто случается со мной)?
Кроме того, части N =< 0, fail;
избыточны? Они кажутся излишними, но я не могу быть уверен, пока не получу что-то работающее.
Изменить: я использую GNU Prolog.