Question

Scheme Programming - Racket R5RS

Longest Non-Decreasing Subsequence

You will write two Scheme functions that compute a longest non-decreasing subsequence from a list of numbers. For example, if you type

> (lis '(1 2 3 2 4 1 2))

you might get

(1 2 3 4)

Note that there may be more than one longest non-decreasing subsequence. In the above example, your program might also find (1 2 2 4) or (1 2 2 2).

You should concentrate first on simply getting a solution working. One possibility is simple exhaustive search:

for i := n downto 1, where n is the length of the input list

    for all i-element sublists s of the input list

      if s is a non-decreasing sequence of numbers

         print s and quit

Unfortunately, this algorithm is inefficient. The number of distinct sublists of a given list is 2ⁿ (to generate a sublist, we have two choices -- include or exclude -- for each of n elements).

Once you have a simple version running using the above algorithm, your next task is to find a polynomial-time solution.

To avoid typing long lists at the interpreter line, I suggest you create a few sample arguments in a file, say my_lists.rkt. You can create those definitions in DrRacket's definition window and save them in file my_lists.rkt. For example, if my_lists.rkt may contain definitions

(define list1 '(1 2 3 2 4 1 2))

(define list2 '(2 4 3 1 2 1))

you can call

> (lis list1)

and

> (lis list2)

• Write two functions, lis_slow, which implements the pseudocode above and lis_fast, which implements a polynomial solution. Both lis_slow and lis_fast consume a list of numbers as arguments and produce a list as a result, as shown in the lis examples above. Include functions lis_slow and lis_fast in your lis.rkt file.
• You are not allowed to use imperative features of Scheme. Do not use side-effecting functions (i.e., functions with exclamation point in their names such as set!), sequencing, iteration (e.g., do, for-each) or vectors. Do not use input/output mechanisms other than the regular read-eval-print loop. (You may find imperative features useful for debugging. That's ok, but get them out of your code before you turn anything in.) Code the algorithms in terms of the purely functional subset of Scheme we have covered in class, however you are allowed to use some additional built-in list operations, e.g., reverse, list-ref, etc.
• You must comment your code! You are required to write comments using the style described here.

Answer 1

#lang racket/base
(require data/gvector)
 
(define (gvector-last gv)
  (gvector-ref gv (sub1 (gvector-count gv))))
 
(define (lis-patience-sort input-list)
  (let ([piles (gvector)])
    (for ([item (in-list input-list)])
      (insert-item! piles item))
    (reverse (gvector-last piles))))
 
(define (insert-item! piles item)
  (if (zero? (gvector-count piles))
      (gvector-add! piles (cons item '()))
      (cond
        [(not (<= item (car (gvector-last piles))))
         (gvector-add! piles (cons item (gvector-last piles)))]
        [(<= item (car (gvector-ref piles 0)))
         (gvector-set! piles 0 (cons item '()))]
        [else (let loop ([first 1] [last (sub1 (gvector-count piles))])
                (if (= first last)
                    (gvector-set! piles first (cons item (gvector-ref piles (sub1 first))))
                    (let ([middle (quotient (+ first last) 2)])
                      (if (<= item (car (gvector-ref piles middle)))
                          (loop first middle)
                          (loop (add1 middle) last)))))])))

Output:

'(2 4 5)
'(0 2 6 9 11 15)

Note: Plzzz don' t give dislike.....Plzzz comment if u have any problem i will try to resolve it.......