Как сделать Prolog способным генерировать все возможные решения для запроса

Question

Я хотел бы иметь возможность генерировать все возможные списки элементов, с 'и' между двумя последними элементами (как в обычном языке). В любом списке не должно быть повторяющихся элементов. Итак, "три, два и четыре" - это правильный список, как и "два и один", или "пять, три, четыре, один и два". Я не ищу одноэлементные списки.

Я написал следующую программу. Когда я запрашиваю у Пролога конкретный список, он сообщит мне правильно, если это правильный список. Однако, когда я запрашиваю список (X), он генерирует списки только с двумя элементами.

Может ли кто-нибудь предложить способ заставить его генерировать все возможные списки, используя данные элементы? Спасибо!

У меня есть такие факты, как

element([one]).
element([two]).
element([three]).
element([four]), etc. etc.

Мои предикаты для создания списка L:

list(L):-
     element(E1),
     element(E2),
     E1 \= E2,
     append(E1, [and], X),
     append(X, E2, L).

%recursive case
list(L):-
     element(E),
     append(E, [','], X),
     append(X, Y, L),
     list(Y),
     not_in(E, Y).

not_in([X], [Y]):- X \= Y.
not_in([X], [H|T]):-
     [X] \= [H],
     not_in([X], T).

Answer 1

Зацикливание ошибка

Ваш код зацикливается, потому что list(L) определяется с точки зрения list(Y) (рекурсивное определение). element(E) выбирает первое вхождение, т.е. [one], а затем добавляет это в новый список Y, до бесконечности. Вы проверяете это E не повторяется в Y в последней строке, но цикл появляется перед этим.

list(L):-
  element(E),
  append(E, [','], X),
  append(X, Y, L),
  list(Y),
  not_in(E, Y).

Правильная реализация

С использованием append/3 несколько раз может запутаться, я использую DCG здесь. Хитрость заключается в том, чтобы держать список вокруг уже используемых элементов, чтобы мы могли заранее проверить наличие дубликатов. Это позволяет избежать зацикливания при попытке проверить это впоследствии.

list -->
  list([]).

list(T) -->
  element(T, H),
  [and],
  element([H|T], _).
list(T) -->
  element(T, H),
  [','],
  list([H|T]).

element(L, X) -->
  cardinal(X),
  {\+ memberchk(X, L)}.

cardinal(1) --> [one].
cardinal(2) --> [two].
cardinal(3) --> [three].
cardinal(4) --> [four].

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

?- phrase(list, List).
List = [one, and, two] ;
...
List = [one, ',', two, ',', three, and, four] ;
...
List = [four, ',', three, ',', two, and, one] ;
false