Home > Archive > Prolog > May 2004 > add numbers to list
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
add numbers to list
|
|
|
| Hi,
I need help with this simple predicate.
AddnOrder(L1,L2,L3) :-
L1 = [0,2,4,7,9]
L2=[1,3,5,8,10]
Then I would like L3 as an output which should be
L3=[0,1,2,3,4,5,6,7,8,9,10]
How do I compare each item from L1 with items from L2?
Thanks.
Regards,
Ruth
| |
|
| Hi!
"Neil" <neilyork82@yahoo.com> wrote in message
news:c77qe3$3b$1@news.epidc.co.kr...
> Hi,
> I need help with this simple predicate.
>
> AddnOrder(L1,L2,L3) :-
>
> L1 = [0,2,4,7,9]
>
> L2=[1,3,5,8,10]
>
> Then I would like L3 as an output which should be
> L3=[0,1,2,3,4,5,6,7,8,9,10]
In your example, L1 and L2 are both ordered, but you did not
write in your question, if that is generally true, or just by accident.
If L1 and L2 are not ordered, just concatenate them, and use
whatever sorting algorithm you prefer.
If L1 and L2 are both ordered, there is a simpler way, just compare
the first elements of L1 and L2, put the smaller one in the result list,
cut this item from L1 or L2, and than continue the algorithm until
all elements are processed. For example:
merge([], L, L) :- !.
merge(L, [], L) :- !.
merge([A|L1], [B|L2], [A|L3]) :- A<B, !, merge(L1, [B|L2], L3).
merge(L1, [X|L2], [X|L3]) :- merge(L1, L2, L3).
Dave
| |
|
|
Hi Dave,
Thanks! L1 is unodered and L2 is ordered.
When I tried your code, it outputs the wrong result.
merge([3,2,7,6],[1,3,4,5,8],L)?
= [1, 3, 3, 2, 4, 5, 7, 6, 8]
??
Regards,
Neil
| |
|
| No, my original code works only if both
L1 and L2 are sorted. If L1 is unsorted and L2
is sorted, I guess the best way to merge them, is
to insert each item of L1 to L2 one by one, eg:
% If L1 is empty then L3 = L2
add_order([], L, L).
% Insert the first item with add_item, then carry on
% calling add_order until L1 gets empty.
add_order([A|T], L2, L3) :-
add_item(L2, A, L22),
add_order(T, L22, L3).
% add_item(L1, X, L2).
% Adding item X to L1 produces L2, where both L1 and L2 are
% sorted.
add_item([A|T], X, [A|L]) :-
A<X, !,
add_item(T, X, L).
add_item(L, X, [X|L]).
This one works, if L1 is unsorted, but L2 must still be sorted:
| ?- add_order([1,3,5,7,9],[2,4,6,8,10], L3).
L3 = [1,2,3,4,5,6,7,8,9,10] ? ;
no
| ?- add_order([9,5,3,7,1],[2,4,6,8,10], L3).
L3 = [1,2,3,4,5,6,7,8,9,10] ? ;
no
Dave
"Neil" <neilyork82@yahoo.com> wrote in message
news:c788cj$5dv$1@news.epidc.co.kr...
>
> Hi Dave,
>
> Thanks! L1 is unodered and L2 is ordered.
> When I tried your code, it outputs the wrong result.
>
> merge([3,2,7,6],[1,3,4,5,8],L)?
>
> = [1, 3, 3, 2, 4, 5, 7, 6, 8]
>
> ??
>
> Regards,
> Neil
>
>
| |
| Stephan Lehmke 2004-05-12, 9:20 pm |
| In article <c7cvfr$j80$1@namru.matavnet.hu>,
"Dave" <vd419ll@freemail.hu> writes:
> No, my original code works only if both
> L1 and L2 are sorted. If L1 is unsorted and L2
> is sorted, I guess the best way to merge them, is
> to insert each item of L1 to L2 one by one, eg:
I doubt that. If L1 has k elements and L2 has n, then
your suggestion has asymptotic worst case running time
O(k*(n+k)) while first sorting L1 and then merging with
L2 has O(k * log k + n), which is always smaller.
regards
Stephan
| |
| flapper 2004-05-12, 9:20 pm |
| Stephan Lehmke wrote:
> In article <c7cvfr$j80$1@namru.matavnet.hu>,
> "Dave" <vd419ll@freemail.hu> writes:
>
>
>
> I doubt that. If L1 has k elements and L2 has n, then
> your suggestion has asymptotic worst case running time
> O(k*(n+k)) while first sorting L1 and then merging with
> L2 has O(k * log k + n), which is always smaller.
>
> regards
> Stephan
Shouldn't that be O( k*log(k) + k*n ) ?
I can see how you get
cost( sort list size k ) = k*log(k)
but I don't see how then you get
cost( combine sorted list size k with sorted list size n ) = n
| |
| Stephan Lehmke 2004-05-12, 9:20 pm |
| In article <Wzymc.10130$Fo4.126759@typhoon.sonic.net>,
flapper <not@u.v.w.xINVALID> writes:
>
> Shouldn't that be O( k*log(k) + k*n ) ?
>
> I can see how you get
>
> cost( sort list size k ) = k*log(k)
>
> but I don't see how then you get
>
> cost( combine sorted list size k with sorted list size n ) = n
Well, a single merge inspects each element of each list at most once.
In principle, this would need O(k + n) time, but k is
dominated by k * log k.
regards
Stephan
| |
|
|
"Stephan Lehmke" <Stephan.Lehmke@ls1.cs.uni-dortmund.de> wrote in message
news:c7dk47$fek$1@fbi-news.cs.Uni-Dortmund.DE...
> In article <c7cvfr$j80$1@namru.matavnet.hu>,
> "Dave" <vd419ll@freemail.hu> writes:
>
> I doubt that. If L1 has k elements and L2 has n, then
> your suggestion has asymptotic worst case running time
> O(k*(n+k)) while first sorting L1 and then merging with
> L2 has O(k * log k + n), which is always smaller.
It's true, I should have said easiest way instead of best way,
however standard prolog lists are like linked lists, and
do not have an O(1) way to access the nth element. In prolog
finding the nth element of a list requires O(n) steps. As far as I know
O(n * log n) sorting algoritms assume that the nth element can
be accessed in O(1) time like an array indexing in C.
Dave
| |
| Stephan Lehmke 2004-05-12, 9:20 pm |
| In article <c7g95a$a53$1@namru.matavnet.hu>,
"Dave" <vd419ll@freemail.hu> writes:
>
> "Stephan Lehmke" <Stephan.Lehmke@ls1.cs.uni-dortmund.de> wrote in message
> news:c7dk47$fek$1@fbi-news.cs.Uni-Dortmund.DE...
>
> It's true, I should have said easiest way instead of best way,
> however standard prolog lists are like linked lists, and
> do not have an O(1) way to access the nth element. In prolog
> finding the nth element of a list requires O(n) steps. As far as I know
> O(n * log n) sorting algoritms assume that the nth element can
> be accessed in O(1) time like an array indexing in C.
No. Bratko for instance has a nice O(n log n) version of QuickSort
using difference lists.
Furthermore it is not clear that when you call sort()
in Prolog something is executed which was implemented
in Prolog...
regards
Stephan
| |
| bart demoen 2004-05-12, 9:20 pm |
| Stephan Lehmke wrote:
> No. Bratko for instance has a nice O(n log n) version of QuickSort
> using difference lists.
Quick sort is O(n log n) expected, but O(n^2) worst case.
Which makes quick sort into a "not very good" sorting algo.
(have a look at http://en.wikipedia.org/wiki/Sort_algorithm)
> Furthermore it is not clear that when you call sort()
> in Prolog something is executed which was implemented
> in Prolog...
It is very clear if you care to have look at the
libraries, or if you care to compare your own Prolog version
of sort with the builtin one (and you notice that by writing it in
plain Prolog, there is no way you can win from the builtin one,
especially for long lists).
Quoting myself from a 3 year old e-mail exchange with Mats
-- the fastest sort in C (for Prolog lists of Prolog integers) is only
-- between a factor 4 and 5 faster than the fastest sort in Prolog
-- - and this in an emulator - I don't think the situation is very bad
Yap, SICStus, XSB and ilProlog have a "native" (non-Prolog) sort
implementation, as undoubtly have many other implementations.
Cheers
Bart Demoen
| |
| flapper 2004-05-12, 9:20 pm |
| Stephan Lehmke wrote:
> In article <Wzymc.10130$Fo4.126759@typhoon.sonic.net>,
> flapper <not@u.v.w.xINVALID> writes:
>
>
>
> Well, a single merge inspects each element of each list at most once.
>
> In principle, this would need O(k + n) time, but k is
> dominated by k * log k.
>
> regards
> Stephan
I see. Merging two sorted lists of lengths, one of length k and the
other of length n, takes O(k+n) but
O( k*log(k) + (k+n) ) = O( k*(log(k)+1) + n) = O( k*log(k) + n )
which IIRC was being compared to inserting each member of an unsorted
list into a sorted list one by one, which takes
O( k*(k+n) ) = O( k*k + k*n )
Wow.
That got my attention.
Thank you.
Regards,
Bill
--
sequitur AT sonic DOT net
| |
| Stephan Lehmke 2004-05-12, 9:20 pm |
| In article <1083958546.238085@seven.kulnet.kuleuven.ac.be>,
bart demoen <bmd@cs.kuleuven.ac.be> writes:
> Stephan Lehmke wrote:
>
> Quick sort is O(n log n) expected, but O(n^2) worst case.
> Which makes quick sort into a "not very good" sorting algo.
> (have a look at http://en.wikipedia.org/wiki/Sort_algorithm)
Ah well. If all you care about is asymptotic behaviour, then
(as also mentioned on the Wiki site) it's possible to choose
the median in O(n) time, making also the worst case running
time of quicksort O(n log n).
But I didn't really want to argue for quicksort; in fact in
PROLOG (where native list sorting won't be in situ anyway)
probably merge sort is the better choice.
regards
Stephan
| |
| bart demoen 2004-05-12, 9:20 pm |
| Stephan Lehmke wrote:
> Ah well. If all you care about is asymptotic behaviour, then
> (as also mentioned on the Wiki site) it's possible to choose
> the median in O(n) time, making also the worst case running
> time of quicksort O(n log n).
Indeed.
> But I didn't really want to argue for quicksort; in fact in
> PROLOG (where native list sorting won't be in situ anyway)
> probably merge sort is the better choice.
Two things:
- typically, (good) native list sorting makes one copy of the
list and then goes on in situ. Real in situ could only be done when
information like (di,uo) were available and exploitable - i.e. Mercury,
enhanced with compile time garbage collection. Wait another year, and
I bet it will be in the release !
- as area co-editor of the Logic Programming Pearls Section of
TPLP, I can tell you: a well written comparative study of sorting
algorithms implemented in Prolog (performance, space ...), would make
a good contribution for this section - but don't underestimate it: it is
a daunting task to do it rigth.
Cheers
Bart Demoen
|
|
|
|
|