0

I am learning Prolog and trying to solve some of the exercises from the book "The Art of Prolog". Someone, please help me to solve Q 3.3.1.(vi), below is the problem -

Q. Write a logic program for kth_largest (Xs, K) that implements the linear algorithm for finding the kth largest element K of a list Xs. The algorithm has the following steps:

  • Break the list into groups of five elements.
  • Efficiently find the median of each of the groups, which can be done with a fixed number of comparisons.
  • Recursively find the median of the medians.
  • Partition the original list with respect to the median of medians.
  • Recursively find the kth largest element in the appropriate smaller list.

Any help will be appreciated. Thanks in advance.

false
  • 10,264
  • 13
  • 101
  • 209
user3756005
  • 43
  • 1
  • 6
  • 2
    They already broke the problem down into steps. Which step are you having trouble with and what have you tried? – lurker Feb 07 '18 at 03:13
  • Yes I know the algorithm. But I am struggling to implement it in Prolog. As I have started learning prolog from last month. I am not able to break the list after every 5 elements and create multiple groups from it. – user3756005 Feb 07 '18 at 03:33
  • @user3756005 - That's actually really simple. Create a predicate that receives a list like `split/2` and then do this in your header `split([],[]). split([A,B,C,D,E|T], [[A,B,C,D,E]|Empty]) :- split(T,Empty).` What this does is take the first 5 elements from the Head of the list, and passes the Tail on to a recursive function that does the same for the next 5 elements until the list is empty. Here's a short resource that explains well how [lists](http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse13) work. – G_V Feb 07 '18 at 08:38

0 Answers0