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)