CODEWITHSUNDEEP
listschemesublist
Follen Fang
Follen Fang

Reputation: 33

Return a index of sublist in scheme

Well I am a Scheme newbie and I`m reading SICP right now.I found a question on a website.I took 2 days to think about it but still no idea could u guys please help with that?

Question following:

A common task in computer science is finding instances of a pattern in a data set. In this problem, you will write a procedure (find-sublist space sublist) that returns a list of the indices of the start of all instances of the sublist in the space in order. Note that instances of the sublist may overlap as in one of the examples given []. If the space contains lists, you do not need to find the sublist in the lists in the space as in one of the examples below [*]. You may assume that the sublist is not empty.

Examples:
(find-sublist '(7 1 2 3 4 1 2 1 2) '(1 2)) ; should return '(2 6 8)
(find-sublist '(“a” “b” “c” “b” “d”) '(“d”)) ; should return '(5)
(find-sublist '((1 2) (3 4) (5 . 6) 7 #f) '((3 4) (5 . 6))) ; should return '(2)
(find-sublist '(1 1 1 2 1) '(1 1)) ; [*] should return '(1 2)
(find-sublist '(9 1 2 3 (5 1 2 3) 1 2 3) '(1 2 3)) ; [**]should return '(2 6)
(find-sublist '() '(#t #f #f)) ; should return '()

Upvotes: 1

Views: 1202

Answers (2)

GoZoner
GoZoner

Reputation: 70145

You ask yourself the question: does the first element of my list match the pattern? If so, record the index. If you solve that problem then you apply the same logic to the remainder of the list. Here is a simple solution.

(define (find-sublist list sub)
  (define (sublist? list sub)
    (or (null? sub)
        (and (not (null? list))
             (equal? (car sub) (car list))
             (sublist? (cdr list) (cdr sub)))))

  (let walking ((list list) (index 1) (indices '()))
    (if (null? list)
        (reverse indices)
        (walking (cdr list)
                 (+ 1 index)
                 (if (sublist? list sub)
                     (cons index indices)
                     indices)))))

This uses a technique known as 'tail recursion' which makes it computationally equivalent to iteration.

Upvotes: 0

Óscar López
Óscar López

Reputation: 236004

I'll give you some hints to find the answer on your own, fill-in the blanks. The first step is to split the problem in two, first a predicate that tells if sublst is in lst, starting from the first position in lst:

(define (sublist? lst sublst)
  (cond (<???> <???>)  ; if sublst is empty return true
        ((and <???>    ; if lst is not empty and
              <???>)   ; the first element is equal in both lists
         (sublist? <???> <???>)) ; advance recursion over both lists
        (else <???>))) ; otherwise return false

Now the main procedure: this one checks at each position in space if there's a sublist starting just there (use the previous procedure). If so, build a list passing as element the current index. Notice that we need to keep track of the current index in an extra parameter:

(define (find-sublist space sublist)
  (let loop ((space space)            ; initialize iteration variables
             (idx 1))
    (cond (<???> <???>)               ; if space is empty return the empty list
          ; if the list starting at current position is the sublist
          ((sublist? space sublist) 
           (cons <???>                ; cons current index, advance recursion
                 (loop <???> <???>))) ; over the list and increment index
          (else                       ; otherwise just advance the recursion
           (loop <???> <???>)))))     ; same as before

Upvotes: 3

Related Questions