[Exercise]Is this list a sublist?

Joe

In your language of choice, pick a simple ordered container of objects (arrays, list, vectors, strings, you-name-it ...). Let C1 and C2 be two instances of this container. The goal of this exercise is to write a function that takes C1 and C2 as paramters and returns a boolean whose value is True if C1 is a ~~subset~~ ~~subsequence~~ subword of C2 and False otherwise.

Here are some examples you could use to validate your code:

C1=(2, 39) C2=(3, 20, 2, 39, 93, 2) -> True
C1=(10, 0) C2=(5, 10, 3, 0, 9) -> False
C1=(4, 50, 3) C2=(3, 87, 4, 50) -> False

Remarks

Most languages implement this functionality either natively (like the in operator in Python on strings) or through specialized libraries (like <string.h> in C). It goes without saying that you shouldn't use those.
This exercise is a bit easier than the ones I usually post. It can be a good entry point for members looking to start participating in our Programming Exercises series but don't know where to start.
If anyone feels the exercise is not challenging enough, answer the question in your weakest language (or a language you're trying to learn).

geek

Subsequence instead of subset, based on the examples you have given.

Joe

~~Corrected~~. Are you posting some code this time?
EDIT: Well my examples do not follow exactly the definition of Subsequence as the sub-element has to be a consecutive sequence found inside the element (look at my second example).

This paragraph seems to show that the word I'm looking for is substring, or subword. I'm using the latter because string has a very localized connotation for programmers and I want the function to take any type of sequence as input.

Anyway, thanks for helping me get my (badly needed) formalism straight in formulating my problems.

Joe

My answer in Scheme (clearly our syntax coloring system is not familiar with this language):

(define nil '()) ;;'# This whole line is a hack to improve syntax coloring.

(define (pattern-matcher pattern)
  ;; #Returns a function lambda (target) that returns #t if pattern is found
  ;; #in the beggining of target, and #f otherwise.
  (lambda (target)
    (cond ((and (eq? target nil) (not (eq? pattern nil))) #f)
	  ((eq? pattern nil) #t)
	  ((not (= (car target) (car pattern))) #f)
	  (else ((pattern-matcher (cdr pattern)) (cdr target))))))

(define (sublist? C1 C2)
  ;; #iterates over C2 until it finds a substring that matches C1
  ;; #returns #t if match is found, and #f if nothing is.
  (cond ((eq? C2 nil) #f)
	(((pattern-matcher C1) C2) #t)
	(else (sublist? C1 (cdr C2)))))

geek

Here's one in Haskell:

subword :: (Eq a) => [a] -> [a] -> Bool -> Bool
subword [] _ _ = True
subword _ [] _ = False
subword (x:xs) (y:ys) b = ((x == y) && (subword xs ys False)) || (b && (subword (x:xs) ys True))

> subword [1,2,3] [1,1,2,2,3,3] True
False
> subword [1,2,3] [1,1,2,3,3] True
True

arithma

@geek: I didn't get this subexpression:

subword (x:xs) ys

x:xs is equivalent to tail(xs) if "tail" exists..?

geek

@arithma: The last line can be written alternatively as:

subword xs ys b = (((head xs) == (head y)) && (subword (tail xs) (tail ys) False)) || (b && (subword xs (tail ys) True))

[inlinecode]x:xs[/inlinecode] is equivalent to [inlinecode]head:tail[/inlinecode] with [inlinecode]head = x[/inlinecode] and [inlinecode]tail = xs[/inlinecode]

@samer: Can we add support for inline code please?

Ayman

My first python one liner ^^

checkSub = lambda seq,subq: len(['t' for i,val in enumerate(seq) if cmp(seq[i:(len(subq)+i)],subq) == 0]) > 0

print checkSub((3, 20, 2, 39, 93, 2),(93,2))

Joe

Nice one Ayman!

For the record, you don't need to [inlinecode]enumerate[/inlinecode] the sequence since you're only using the index. Enumerating can be costly in case of very large sequences (although Python does deal with it lazily). I would write something more like this:

checkSub = lambda seq,subq: len(['t' for i in xrange(len(seq)) if cmp(seq[i:(len(subq)+i)],subq) == 0]) > 0

Ayman

@rahmu ah I see you're right, thanks for the tip! :)