Hi all,
I wanted to know how can i check if the 2 lists have exact number of
elements in them .
So that if this is true it returns true.the order of elements in each
lists can be different.
(a b c d) ==(a d b c)
but,
(a d c d) !=( a b c d e )
Any suggestions
thanks,
Am
Maybe length does what you want:
(defun same-lenths-p (list-1 list-2)
(= (length list-1) (length list-2)))
If you need to do the check for several lists you could do something
like:
(defun same-lenghts-p (&rest lists)
(apply #'=
(loop for list in lists collect (length list))))
André
--
André Thieme wrote:
> Maybe length does what you want:
Emphasis on "maybe."
The idea of using LENGTH on lists is generally a bad sign for
performance. In this particular case, LENGTH will take time
proportional to the *longer* of the two lists, no matter how short the
first is.
> (defun same-lenths-p (list-1 list-2)
> (= (length list-1) (length list-2)))
> If you need to do the check for several lists you could do something
> like:
> (defun same-lenghts-p (&rest lists)
> (apply #'=
> (loop for list in lists collect (length list))))
This has the same flaw.
I don't want to post a homework solution, but the basic principle is
clear: walk down both lists. When *any* of the lists comes to an end,
unless *every other* list has come to an end at the same time, the
lists are different lengths. As a bonus, one might return the length by
counting on the way down.
I believe this can be extended even to cover the case when all lists
are circular, using the standard trick to detect circularity in the
list structure. I.e., if any list is detected to be circular, all must
be circular. It may take a long time, of course, to determine if a long
list is not circular, but that's probably better than an infinite loop.
··············@hotmail.com <············@gmail.com> wrote:
+---------------
| I don't want to post a homework solution, but the basic principle is
| clear: walk down both lists. When *any* of the lists comes to an end,
| unless *every other* list has come to an end at the same time, the
| lists are different lengths. As a bonus, one might return the length by
| counting on the way down.
+---------------
Yup. But...
+---------------
| I believe this can be extended even to cover the case when all lists
| are circular, using the standard trick to detect circularity in the
| list structure. I.e., if any list is detected to be circular, all must
| be circular.
+---------------
Unfortunately, it's not that simple. While what I think you meant
to say works as far as it goes -- that is, if any list is detected
to be circular, one can require that all other lists detect circularity
at the same step -- it still doesn't ensure that the lists are all
of the same "shape". For example, the following two lists are detected
as being equal in "length" and content by the naive tortoise & hare
algorithm [two-pointer trick]:
(0 0 0 0 0 0 0 0 0 . #1=(0 0 . #1#))
(0 0 0 0 0 0 . #1=(0 0 0 0 0 . #1#))
as are the following pair:
(0 1 2 3 4 2 3 4 . #1=(2 3 4 . #1#))
(0 1 . #1=(2 3 4 2 3 4 2 3 4 . #1#))
Yet both the initial prefix and the periodicity of the circular parts
of each pair of lists are different, though circularity is detected
at the same step and the same list items are compared at each step.
So if "shape" is not considered, each pair could be considered to be
in some sense "equal"; but if "shape" is important, they aren't.
Exercise for the reader: given two circular lists for which the
classical tortoise & hare algorithm declares circularity at the
same time, what else needs needs to be done to determine whether
the prefixes and/or the circular tails are/aren't of the same length?
[Hint: Google is your friend.]
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> ··············@hotmail.com <············@gmail.com> wrote:
> +---------------
> | I don't want to post a homework solution, but the basic principle is
> | clear: walk down both lists. When *any* of the lists comes to an end,
> | unless *every other* list has come to an end at the same time, the
> | lists are different lengths. As a bonus, one might return the length by
> | counting on the way down.
> +---------------
>
> Yup. But...
>
> +---------------
> | I believe this can be extended even to cover the case when all lists
> | are circular, using the standard trick to detect circularity in the
> | list structure. I.e., if any list is detected to be circular, all must
> | be circular.
> +---------------
>
> Unfortunately, it's not that simple. While what I think you meant
> to say works as far as it goes -- that is, if any list is detected
> to be circular, one can require that all other lists detect circularity
> at the same step -- it still doesn't ensure that the lists are all
> of the same "shape".
<snip>
Perhaps my statement wasn't clear. I was only trying to put up a
firewall against the pathological case where all the arguments happen
to be "infinite" in length; i.e. as soon as one detects one list is
circular, i.e. "infinitely long", one then switches modes to check that
all of the other lists are also "infinitely long", as opposed to a
naive algorithm that might keep cdring down all the infinite lists
forever.
That is, your requirement "at the same step" was not part of what I had
in mind.
I suppose there are clever ways to test for more general isomorphism,
but I haven't really thought about it. One could also decide that
infinite lists are not equal in length with any other lists, and simply
return nil. I don't know which is most useful in practice.
··········@yahoo.co.in" <·········@yahoo.co.in> writes:
> Hi all,
> I wanted to know how can i check if the 2 lists have exact number of
> elements in them .
> So that if this is true it returns true.the order of elements in each
> lists can be different.
> (a b c d) ==(a d b c)
> but,
> (a d c d) !=( a b c d e )
> Any suggestions
You've underspecified. I may interpret it as:
If the order doesn't matter, then you have sets.
(defun set-equal (a b) (and (subsetp a b) (subsetp b a)))
You are adding a constraint that doesn't exist in CL: you want the
lists representing the sets to have the same number of elements. So be it:
(defun my-strange-set-equal (a b)
(and (= (length a) (length b)) (set-equal a b)))
(map nil (lambda (a b)
(map nil (lambda (f)
(format t "(~20A ~S ~S) --> ~A~%" f a b (funcall f a b)))
'(set-equal my-strange-set-equal)))
'(() (a b) (a b c) (a b c) (a b b c) (a b c d) (a b c))
'(() () (a b c) (b a c) (a c b c) (a b b d) (a b c a b c)))
(SET-EQUAL NIL NIL) --> T
(MY-STRANGE-SET-EQUAL NIL NIL) --> T
(SET-EQUAL (A B) NIL) --> NIL
(MY-STRANGE-SET-EQUAL (A B) NIL) --> NIL
(SET-EQUAL (A B C) (A B C)) --> T
(MY-STRANGE-SET-EQUAL (A B C) (A B C)) --> T
(SET-EQUAL (A B C) (B A C)) --> T
(MY-STRANGE-SET-EQUAL (A B C) (B A C)) --> T
(SET-EQUAL (A B B C) (A C B C)) --> T
(MY-STRANGE-SET-EQUAL (A B B C) (A C B C)) --> T
(SET-EQUAL (A B C D) (A B B D)) --> NIL
(MY-STRANGE-SET-EQUAL (A B C D) (A B B D)) --> NIL
(SET-EQUAL (A B C) (A B C A B C)) --> T
(MY-STRANGE-SET-EQUAL (A B C) (A B C A B C)) --> NIL
NIL
--
__Pascal Bourguignon__ http://www.informatimago.com/
Wanna go outside.
Oh, no! Help! I got outside!
Let me back inside!
But the issue is i have to only perform this operation with recursion
and not using any inbuild functions in LISP. can this be performed
using recursion only...
Please help...
·········@yahoo.co.in schrieb:
> But the issue is i have to only perform this operation with recursion
> and not using any inbuild functions in LISP. can this be performed
> using recursion only...
> Please help...
Hmm, why can't you use any functions that come with Lisp?
Won't the program work anymore?
No no, you don't need recursion.
André
--
In article <························@g43g2000cwa.googlegroups.com>,
··········@yahoo.co.in" <·········@yahoo.co.in> wrote:
> But the issue is i have to only perform this operation with recursion
> and not using any inbuild functions in LISP. can this be performed
> using recursion only...
> Please help...
How do you expect us to get a good mark on your homework if you don't
copy the problem completely and tell us what chapter it's covering?
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
··········@yahoo.co.in" <·········@yahoo.co.in> writes:
> But the issue is i have to only perform this operation with recursion
> and not using any inbuild functions in LISP. can this be performed
> using recursion only...
> Please help...
This is not possible to write a lisp program without using any inbuilt function.
Or we could re-implement our own lisp, but then you'd be using your
own inbuilt lisp functions.
--
__Pascal Bourguignon__ http://www.informatimago.com/
HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.