Possible list permutation using a given formula

Question

I am trying to get my head wrap around lists in Prolog. To do this I am trying to create a sort of game. You pass in a list of numbers 1-9 that can be repeated, the list can be any length. The rules are that starting from the first element(e) you can only move to e+2 or e+3 until you get to the end. The goal is to "land" on the highest numbers. In essence it is kind of like hopscotch. The problem I am running into is determining all the possible permutation for paths. So far I have the following.

paths([], []). %empty list returns empty list
paths([X], [X]). %list with one element returns that one element
paths([X1, X2], [X1]). %list with 2 elements returns the first element
paths([X1, X2, X3], [X1,X3]). %list with three elements returns the first and third element
paths() :- % the recursive case for a list with 4+ elements

An list to use would be: [1,2,3,4,5,6,8,7,9,3,6,5,7,8,9] I need to determine all possible paths using the rule mentioned about. I wish lists could be indexed in Prolog :(

Any logic guidance would be appreciated.

Answer 1

The requirements aren't completely clear, but it seems that:

• The second argument is required to have the same first element as the first argument (you "hop" on the first "square" first always, using your hopscotch metaphore)

• You aren't requiring that the last element of the first list be the last element of the second list (you aren't requiring that you "land on" the last "square").

• An empty list succeeds with an empty list result (rather than just failing on an empty list - which is another valid approach).

Then this could be implemented as follows. You do not need many explicit 2- and 3-element list cases since they are handled by the recursive clause and simpler base cases.

path([], []).
path([X], [X]).
path([X,_|T], [X|R]) :-   % hop over 1 element
    path(T, R).
path([X,_,_|T], [X|R]) :- % hop over 2 elements
    path(T, R).

For a simple example:

| ?- path([1,2,3,4,5,6], R).

R = [1,3,5] ? ;

R = [1,3,6] ? ;

R = [1,4,6] ? ;

R = [1,4]

yes

If I don't have your requirements exactly right, you should be able to adjust this to suit your needs as it shows how to handle a recursive case. It also sounds like you are headed in the direction of trying to optimize the values in your hops, which I shall also leave as an exercise.

This can also be done with a DCG (definite clause grammar)

path([]) --> [].
path([X]) --> [X].
path([X|T]) --> ([X,_] | [X,_,_]), path(T).

Which would be exercised:

| ?- phrase(path(R), [1,2,3,4,5,6]).

R = [1,3,5] ? ;

R = [1,3,6] ? ;

R = [1,4,6] ? ;

R = [1,4] ? ;

(1 ms) no
| ?-

---

In light of the extra requirement that the last step taken must be one that falls within the list, here is an updated version of the path/2 predicate:

path([], []).
path([X], [X]).
path([X,_], [X]).
path([X,_,Y|T], [X|R]) :-   % hop over 1 element
    path([Y|T], R).
path([X,_,_,Y|T], [X|R]) :- % hop over 2 elements
    path([Y|T], R).

Answer 2

%passing in a list and return all possible paths using K+2 or K+3 with K being the first element of the list.
%empty list returns empty list
%list with one element returns that one element
%list with 2 elements returns the first element
%list with three elements returns the first and third element
%list with four/four+ elements needs to be called recursively, prefix them with the first element and append them together
%RL means ReturnList
%FL means FinalList
%List is the appended list containing all the paths
paths([], []). 
paths([X], [[X]]). 
paths([X1, X2], [[X1]]). 
paths([X1, X2, X3], [[X1,X3]]). 
paths([X1, X2, X3, X4 | T], List) :-
   paths([X3,X4|T], RL), paths([X4|T], RL2), 
   prefix_all(X1, RL, FL1), prefix_all(X1, RL2, FL2), 
   append(FL1, FL2, List). 

So if run with the list [1,2,3,4,5] is would produce the following:

| ?- paths([1,2,3,4,5],X). 

X = [[1,3,5],[1,4]] ? ;
no

Answer 3

I think that there is a reason to avoid indexing: simplicity. If you decompose your problem, maybe you could start writing a step/3 predicate like

step([_,X|T],X,T).
step([_,_,X|T],X,T).

and then

paths([],[]).
paths(L,[X|Xs]) :- step(L,X,T), paths(T,Xs).

note: I don't understand very well your game, some example of playground and solution would be welcome.