CODEWITHSUNDEEP
prolog
Max Truedsson
Max Truedsson

Reputation: 23

Finding subsequences from list

Hello i can't figure out how to solve an assignment. I am supposed to find the consecutive element combinations from a list. For example: the list [1,2,3] should give me [1],[2],[3], [1,2], [2,3], [1,2,3] but the problem i have is that my attempt also gives me [1,3]

Code:

subseq([], []).
subseq([H|T], [H|R]) :- subseq(T, R).
subseq([_|T], R) :- subseq(T, R).

Upvotes: 2

Views: 581

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476544

The problem here is that on each element of the given list, you have two clauses:

  1. the second line where you select the item; and
  2. the third line where you do not select the item.

So that means you generate all lists where for every item it is an option to include it, or exclude it.

For a subsequence, the ones defined in your question, it is a different story: you basically have two selection points:

  1. the point where you "start" the subsequence; and
  2. the point where you "stop" the subsequence.

Stopping a subsequence is actually the same as generating a prefix:

myprefix(_, []).
myprefix([H|T], [H|T2]) :-
    myprefix(T, T2).

So now for a subsequence, we only need to branch over the starting point, and then add a prefix of the remaining list, like:

subsequence([H|T], [H|T2]) :-
    myprefix(T, T2).
subsequence([_|T], T2) :-
    subsequence(T, T2).

This then yields the expected:

?- subsequence([1, 2, 3], X).
X = [1] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [2] ;
X = [2, 3] ;
X = [3] ;
false.

Upvotes: 1

Related Questions