CODEWITHSUNDEEP
prolog
hassapikos
hassapikos

Reputation: 69

How to make Prolog able to generate all possible solutions to a query

I'd like to be able to generate all possible lists of elements, with an ‘and’ between the last two elements (as in normal language). There should be no duplicate elements in any list. So ‘three, two, and, four’ is a correct list, as is ‘two and one’, or ‘five, three, four, one, and, two’. I am not looking for single-element lists.

I’ve written the following program. When I query Prolog about a specific list, it will tell me correctly if it is a valid list. However, when I query list(X), it only generates lists with two elements.

Could someone suggest a way to make it generate all possible lists, using the given elements? Thank you!

I have facts such as

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

My predicates to generate a list L are:

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).

Upvotes: 0

Views: 1163

Answers (1)

Wouter Beek
Wouter Beek

Reputation: 3407

Looping bug

Your code loops because list(L) is defined in terms of list(Y) (recursive definition). element(E) picks the first occurrence, i.e. [one], and then prepends this to a new list Y, ad infinitum. You are checking that E does not reoccur in Y in the last line, but the loop appears before that.

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

Correct implementation

Since using append/3 several times can get messy, I am using DCGs here. The trick is to keep a list around of already used elements so that we can check for duplicate occurrences up front. This avoid the looping behavior that occurs when trying to check for this afterwards.

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].

Example of use:

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

Upvotes: 1

Related Questions