Hello Kanen,

When I wrote my last message, I had to guess (a little) as to what exactly you needed. Then today, I thought of another meaning regarding what you said.

When I coded

**sublist?**, I assumed that you wanted to see if a

**big-list** item (which was a list) was a sublist of

**small-list**. Since order matters in lists,

**sublist?** obeys the ordering of the elements of the lists involved. It also assumes that adjacent elements in the corresponding lists are preserved. For instance:

Code: Select all

```
> ;; Order matters
> (sublist? '(3 4) '(0 1 2 3 4))
true
> (sublist? '(4 3) '(0 1 2 3 4))
nil
> ;; Adjacency matters
> (sublist? '(3 4) '(0 1 2 3 3.5 4))
nil
```

But what if you had really meant for the "containment" to not necessarily respect element order or adjacency? Then, a natural way to do that would be to treat the lists as

multisets. In this case, the test then changes from

**sublist?** to

**subset?** (where "set" in this context means multiset, a generalization of proper sets).

If

*that *is what you were really after then please consider the following definitions.

Code: Select all

```
(define (subset? A B)
"Is A a subset of B? (A and B are lists that act as multisets)."
(if (empty? A) true
(empty? B) nil
(letn (sizeA0 (length A) ; size of original A
sizeB0 (length B) ; size of original B
dsize0 (- sizeB0 sizeA0) ; original delta of sizes
sizeA sizeA0 sizeB sizeB0 dsize dsize0)
(while (and (>= dsize 0) (= dsize0 dsize)
(not (empty? A)))
(letn (elt (first A)
cnt (length (find-all elt A)))
(setq A (remove cnt elt A))
(setq B (remove cnt elt B))
(setq sizeA (length A))
(setq sizeB (length B))
(setq dsize (- sizeB sizeA))))
(empty? A))))
```

for which you will need the following definition.

Code: Select all

```
(define (remove HOW-MANY ELT LST)
"Remove as many as HOW-MANY occurences of ELT in LST."
(let (elt-position true)
(while (and elt-position (> HOW-MANY 0))
(when (setq elt-position (find ELT LST))
(pop LST elt-position)
(dec HOW-MANY)))
LST))
```

Now, neither order nor adjacency matter.

Code: Select all

```
> ;; Order doesn't matter now.
> (subset? '(3 4) '(0 1 2 3 4))
true
> (subset? '(4 3) '(0 1 2 3 4))
true
> ;; Adjacency doesn't matter either.
> (subset? '(3 4) '(0 1 2 3 3.5 4))
true
```

It just so happens that, with the given definitions of

**big-list** and

**small-list**, using

**subset?** as the test yields the same answer as using

**sublist?** as the test.

Code: Select all

```
> (map second (filter (fn (b) (subset? (b 0) small-list)) big-list))
(1010)
```

And as before, the functions I defined might not meet your performance standards, so please

bum the code as appropriate. :)

(λx. x x) (λx. x x)