Разбиение большого числа с помощью Пролога - PullRequest
Новая
       8

Разбиение большого числа с помощью Пролога

1 голос
/ 11 февраля 2012

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

1 Ответ

2 голосов
/ 11 февраля 2012

У вас есть одна проблема здесь, со сравнением от N до IH: 

partition(N, [IH|IT], [OH|OT]) :-
  N =< 0, fail;
  N > IH, [...]

Это должно быть N >= IH.

Рассмотрим ваш пример partition(4, [1, 2, 3], X):

  1. Соответствует предикату 3, который в свою очередь проверяет partition(3,[1,2,3],OT)
  2. partition(3,[1,2,3],OT) соответствует третьему предикату, который проверяет partition(2,[1,2,3],OT).
  3. partition(2,[1,2,3],OT) соответствует третьему предикату, который проверяет partition(1,[1,2,3],OT).
  4. partition(1,[1,2,3],OT) соответствует четвертому предикату, , поскольку 1> 1 терпит неудачу . Чеки partition(1,[2,3],OT).
  5. partition(1,[2,3],OT) будет соответствовать четвертому предикату до конца и завершится ошибкой, если список пуст.
...