Re: LOGO-L> Re: apl:deal porting to LOGO

["Tom Lynn" <thl22@cam.ac.uk>]

Sorry to dig even further back in the list, but its taken me this long to 
get an answer ready!  In case you've forgotten, the question was "How do 
you select k items at random from a list?".

The attached files are:

pooldeal.lgo - a 'deal' which selects k items from a list without having to
               count all of the items in the list in advance.

heap.lgo     - a set of library routines which implement a heap
               datastructure and heapsort.  Used by pooldeal.lgo.

heap.txt     - an indepth description of heap.lgo.

heaplib      - a file to put in the library folder with heap.lgo to
               make the code in heap.lgo available in the library.

heaptest.lgo - example code for using the heap library in your own programs

I started by just coding an answer to the question of how to select items 
at random from a list (pooldeal.lgo) and found that in order to make it 
work more efficiently I needed a heap.

The idea of pooldeal is that it goes through a list one item at a time, and 
as it pulls each item out it assigns it a random number (a 'key').  The 
items with the k highest numbers so far go into a pool (stored as a heap).  
To decide whether an item should be put in the pool, its key is compared 
with the lowest key in the pool.  If it is greater, it goes in.  Once all 
the numbers from the list have been compared, the k items in the pool are 
the output.  The heap is used to make it easy/efficient to get the lowest 
of the k highest keys so far.

heap.txt contains a description of heaps and a description of what's 
provided by heap.lgo, so I won't try here.  You will need to edit one line 
of heaplib so that it can find heap.lgo on your hard disk if it isn't in 
"C:\Program Files\MSWLogo\LogoLib".

If anyone has any questions about this I'll be happy to (try to) answer 
them.  Oh, and while I was writing this I found that MSWLogo doesn't like 
empty arrays (it throws "out of space" errors) but UCB Logo doesn't mind 
them.  This means that an empty heap has to be represented by a 1-element 
array, {-}, rather than {}.

Tom
The following section of this message contains a file attachment
prepared for transmission using the Internet MIME message format.
If you are using Pegasus Mail, or any another MIME-compliant system,
you should be able to save it or view it from within your mailer.
If you cannot, please ask your system administrator for assistance.

   ---- File information -----------
     File:  pooldeal.lgo
     Date:  26 Aug 1998, 22:58
     Size:  1687 bytes.
     Type:  Text

pooldeal.lgo

heap.lgo

heap.txt

heaplib

heaptest.lgo