1

Given the letters [a, b, c] generate the list containing all the words of length N, formed out of this letters. For example: 

?- generate(2, L).

should output:

L = [aa, ab, ac, ba, bb, bc, ca, cb, cc].

At first, this seemed like a pretty simple problem, but I've discovered that none of my implementations work.

This is the second implementation, the one that kind of works. 

letter(X) :- member(X, [a, b, c]).

generateWord(0, []) :- !.
generateWord(N, [H|T]) :-
    letter(H), 
    NextN is N - 1,
    generateWord(NextN, T).

generateAtomicWord(N, Word) :-
    generateWord(N, WList),
    atomic_list_concat(WList, Word).

maxSolutions(N, R) :- R is N ** 3.

generate(N, CurrentList, ResultList) :-
    maxSolutions(N, R), 
    length(CurrentList, L),
    L =:= R, 
    append(CurrentList, [], ResultList), !.
generate(N, CurrentList, ResultList) :-
    generateAtomicWord(N, NewWord),
    \+ member(NewWord, CurrentList),
    append(CurrentList, [NewWord], NewList),
    generate(N, NewList, ResultList).

generate(N, ResultList) :- 
    generate(N, [], ResultList).

It kind of works because when given N = 3 the program outputs:

L = [aaa, aab, aac, aba, abb, abc, aca, acb, acc|...]

My first implementation is different, but I can't make it work on any case. 

letter(X) :- member(X, [a, b, c]).

generateWord(0, []) :- !.
generateWord(N, [H|T]) :-
    letter(H), 
    NextN is N - 1,
    generateWord(NextN, T), !.

generateAtomicWord(N, Word) :-
    generateWord(N, WList),
    atomic_list_concat(WList, Word).

maxSolutions(N, R) :- R is N ** 3.

generate(N, [H]) :- generateAtomicWord(N, H).
generate(N, [H|T]) :- 
    generate(N, T),
    length(T, TailLen), 
    maxSolutions(N, M), 
    (TailLen =:= M -> !; 
        generateAtomicWord(N, H),
        \+ member(H, T)).

This one just outputs:

L = [aa]

and when requested for the rest of the solutions it cycles.

The problem must be solved without using predicates such as:

findall, findnsol, bagof, setof, etc...

that find all the solutions.

I've added the tag backtracking because it does resemble a backtracking problem, but I've no idea what a standard implementation might look like in Prolog.

false
  • 10,264
  • 13
  • 101
  • 209
Cosmin Stoian
  • 757
  • 10
  • 15

1 Answers1

0

It kind of works because when given N = 3 the program outputs:

L = [aaa, aab, aac, aba, abb, abc, aca, acb, acc|...]

That is not an error, that is the Prolog interpreter that displays the list in a shorter way. If you hit w when it shows the output, it will show the full list. For more information see this answer.

That being said, you make it too hard. You can first make a predicate that will unify a variable with all possible atoms:

letter(X) :- member(X, [a, b, c]).

word(0, []).
word(N, [C|W]) :-
    N > 0,
    N1 is N-1,
    letter(C),
    word(N1, W).

Now we can generate all possibilities with findall/3 [swi-doc], and use for example maplist/3 [swi-doc] with atomic_list_concat/2 to convert the list to a single atom:

words(N, L) :-
    findall(W, word(N, W), Ws),
    maplist(atomic_list_concat, Ws, L).

For example:

?- words(0, L).
L = [''].

?- words(1, L).
L = [a, b, c].

?- words(2, L).
L = [aa, ab, ac, ba, bb, bc, ca, cb, cc].

?- words(3, L).
L = [aaa, aab, aac, aba, abb, abc, aca, acb, acc|...].

We can generate a list of lists ourselves by updating a "difference" list until all possible words are generated:

wordlist(N, L) :-
    wordlist(N, [], L, []).

wordlist(0, R, [W|T], T) :-
    reverse(R, W),
    !.
wordlist(N, C, L, T) :-
    N > 0,
    N1 is N-1,
    wordfold([a,b,c], N1, C, L, T).

wordfold([], _, _, L, L).
wordfold([C|CS], N1, CT, L, T) :-
    wordlist(N1, [C|CT], L, L2),
    wordfold(CS, N1, CT, L2, T).

For example:

?- wordlist(0, L).
L = [[]].

?- wordlist(1, L).
L = [[a], [b], [c]].

?- wordlist(2, L).
L = [[a, a], [a, b], [a, c], [b, a], [b, b], [b, c], [c, a], [c|...], [...|...]].

You then still need to perform atomic_list_concat on it. I leave that as an exercise.

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555