CODEWITHSUNDEEP
listprolog
Michael Miner
Michael Miner

Reputation: 964

Prolog Choose 3 From List

I have create a prolog program which given a Number a List and Sublist will generate sublists containing N items in each. I am told this can be done with 1 fact and 2 rules. I am given the hint that I chose the first item or I dont which is confusing me. I have the base case and the first case but I hope someone can help me understand the second case.

choose(1, [H], [H]).
choose(N, [H,TL], [H|ST]) :- choose(Less1, TL, ST), Less1 is N-1.

So my third rule I want to choose the second item in the list 

choose(N, [F,S|T], [S|ST]) :- choose(Less1, T, ST), Less1 is N-1.

My last rule however is unbalanced and the whole does not work. Any ideas are greatly appreciated!

Upvotes: 1

Views: 1300

Answers (2)

repeat
repeat

Reputation: 18726

While this previous answer by @madanasta should already point you in the right direction, we extend on it in this answer by using :

:- use_module(library(clpfd)).

We define n_from_chosen/3 like this:

n_from_chosen(0,_,[]).
n_from_chosen(N,[X|Es],[X|Xs]) :-
   N #> 0,
   N #= N0+1,
   n_from_chosen(N0,Es,Xs).
n_from_chosen(N,[_|Es],Xs) :-
   N #> 0,
   n_from_chosen(N,Es,Xs).

Sample query:

?- n_from_chosen(2,[1,2,3,4],Xs).
  Xs = [1,2]
; Xs = [1,3]
; Xs = [1,4]
; Xs = [2,3]
; Xs = [2,4]
; Xs = [3,4]
; false.

How about this more general query?

?- n_from_chosen(N,[1,2,3],Xs).
  N = 0, Xs = []
; N = 1, Xs = [1]
; N = 2, Xs = [1,2]
; N = 3, Xs = [1,2,3]
; N = 2, Xs = [1,  3]
; N = 1, Xs =   [2  ]
; N = 2, Xs =   [2,3]
; N = 1, Xs =     [3]
; false.

Upvotes: 2

madanasta
madanasta

Reputation: 119

The idea behind the first two clauses is correct in principle. However:

  • The first clause is of no use when a sublist of length 1 must be found but the original list is not of length 1. This is problematic.
  • In the second clause, I assume you mean [H|TL].

Given these, a solution to your problem might be:

choose(1, [H|_], [H]).
choose(N, [H|TL], [H|ST]) :- Less1 is N - 1, choose(Less1, TL, ST).
choose(N, [_|T], L) :- choose(N, T, L).

An attempt to explain:

  • The first clause will generate a sublist of length 1 given any list with at least one element: It will simply unify the third argument with a single-element list containing only the head of the original list.
  • The second clause will handle cases when sublists of a length greater than 1 are requested, in which case it will unify the third argument with a list containing the head of the original list and a tail which, thanks to recursion, will be a sublist of the original list's tail of a length equal to the requested length minus 1.
  • The third clause will simply skip over the original list's head and will unify the third argument with a list which, thanks to recursion, will be a sublist of the original list's tail of the requested length.

Thanks to the third clause, Prolog will be able to provide alternative solutions for requested lengths either equal to or greater than 1.

Some results:

?- choose(2, [1,2,3,4], L).
L = [1, 2] ;
L = [1, 3] ;
L = [1, 4] ;
L = [2, 3] ;
L = [2, 4] ;
L = [3, 4] ;
false.

Note that you cannot use this to solve queries with an unbound length variable as you could using @repeat's solution. To achieve that in pure Prolog you would have to change the logic behind the second clause a bit:

choose(N, [H|TL], [H|ST]) :- choose(Less1, TL, ST), N is Less1 + 1.

This might also help clarify how recursion works in this case.

Hope this helps.

(Disclaimer: I am fairly certain that one can provide a far better explanation of how the above solution works (not to mention a better solution).)

Upvotes: 1

Related Questions