CODEWITHSUNDEEP
prologcombinationspermutation
derpnallday
derpnallday

Reputation: 49

Prolog: Finding all possible permutations of a list of elements with only two states

I am trying to instantiate multiple lists in Prolog of elements with only two states, the states being red and blue. Initially, I instantiate a list of elements that are only blue by creating a list of size n:

generate_list(0, []) :- !.
generate_list(N, [H | T]) :-
  N2 is N-1,
  H = blue,
  generate_list(N2, T).

I have also defined a predicate to change the state of colors

flip(blue, red).
flip(red, blue).

I would like to use this predicate to change the color during the instantiation of a new list, however I am stuck on how to approach this problem. The default permutation and combination predicate requires you use separate predefined elements to instantiate the new list, however I have a list of elements already generated.

Upvotes: 0

Views: 483

Answers (1)

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

It's not clear from your question what you mean by "changing" the color "during the instantiation". It would be great if you could update it with a concrete example of what you want.

However, here is something that may or may not go into the direction of what you want:

color(red).
color(blue).

colorlist([]).
colorlist([C|Cs]) :-
    color(C),
    colorlist(Cs).

The definition of colorlist/2 says that its argument is a list, with elements satisfying color/1. Either color is fine, so any list of any permutation of elements from red and blue is a solution. We can use this already to check color lists:

?- colorlist([red, blue, blue]).
true.

And also to try to enumerate them, although the enumeration is not fair, i.e., some things that are solutions (in this case, any list containing blue) will never be generated:

?- colorlist(Cs).
Cs = [] ;
Cs = [red] ;
Cs = [red, red] ;
Cs = [red, red, red] ;
Cs = [red, red, red, red] ;
Cs = [red, red, red, red, red] . % etc.

To solve the fairness problem, we can enumerate by length: First all the length-0 lists, then all the length-1 lists, all the length-2 ones, etc. If we expose the length as a parameter, we get something that at least has the same interface as the predicate you are trying to write:

length_colorlist(N, Cs) :-
    length(Cs, N),
    colorlist(Cs).

This can enumerate solutions fairly and generally:

?- length_colorlist(N, Cs).
N = 0,
Cs = [] ;
N = 1,
Cs = [red] ;
N = 1,
Cs = [blue] ;
N = 2,
Cs = [red, red] ;
N = 2,
Cs = [red, blue] ;
N = 2,
Cs = [blue, red] .

And also answer more specific queries restricted by length:

?- length_colorlist(8, Cs).
Cs = [red, red, red, red, red, red, red, red] ;
Cs = [red, red, red, red, red, red, red, blue] ;
Cs = [red, red, red, red, red, red, blue, red] ;
Cs = [red, red, red, red, red, red, blue, blue] ;
Cs = [red, red, red, red, red, blue, red, red] ;
Cs = [red, red, red, red, red, blue, red, blue] ;
Cs = [red, red, red, red, red, blue, blue, red] ;
Cs = [red, red, red, red, red, blue, blue, blue] ;
Cs = [red, red, red, red, blue, red, red, red] ;
Cs = [red, red, red, red, blue, red, red, blue] .

Note: No cuts needed, and the final definition is built up as a simple composition of more generic, individually useful parts. When stuck on a problem, especially in Prolog, always try to solve individual subparts first. In this case, "how do I define lists (of any length) containing colors?" and "how do I generate lists of specific lengths?" are two distinct subproblems that are best solved separately.

Upvotes: 2

Related Questions