home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / function / 1495 < prev    next >
Encoding:
Text File  |  1993-01-09  |  1.8 KB  |  52 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!pipex!ibmpcug!exnet!dcs.ed.ac.uk!pdc
  3. From: pdc@dcs.ed.ac.uk (Paul Crowley)
  4. Subject: Random permutations, linear time, fully functional?
  5. Message-ID: <C0KG2y.HvE@dcs.ed.ac.uk>
  6. Sender: cnews@dcs.ed.ac.uk (UseNet News Admin)
  7. Reply-To: pdc@dcs.ed.ac.uk (Paul Crowley)
  8. Organization: Edinburgh University
  9. Date: Sat, 9 Jan 1993 02:54:33 GMT
  10. Lines: 40
  11.  
  12. Following a long and heated discussion on the topic in a local
  13. newsgroup in which the local ML experts have come up hands empty
  14. (surprising given this is Edinburgh), I'm looking for fully functional
  15. ways of solving certain permutation problems which imperative languages
  16. like C can solve in linear time.  In particular, I'd like to be able to
  17. compose and invert permutations and generate random ones in linear
  18. time.  If you don't like mixing "random" and "fully functional", you
  19. could always ask for a list of random numbers as input. For example, an
  20. equivalent of this C function would be the best part of a solution:
  21.  
  22. /* 
  23.  * source and result are arrays of integers of length n.
  24.  * For random permutations, source should be made up of a lot of
  25.  * random numbers each between 0 and n-1.
  26.  */
  27.  
  28. void randpermute(source, result, n)
  29. int *source, *result, n;
  30. {
  31.     int i, tmp;
  32.     
  33.     for(i = 0; i < n; i++)
  34.         result[i] = i;
  35.     for(i = 0; i < n; i++) {
  36.         tmp = result[i];
  37.         result[i] = result[source[i]];
  38.         result[source[i]] = tmp;
  39.     }
  40. }
  41.  
  42. The best solution so far take O(n log n) time and involves sorting.  I
  43. believe that Haskell has a way of offering read-only arrays accessible in
  44. O(1) time and that might go some way towards a solution (for example,
  45. they solve composition pretty neatly).
  46.  
  47. Be warned that many of the notables of this department have found banana
  48. peels here...
  49.   __                                _____
  50. \/ o\ Paul Crowley pdc@dcs.ed.ac.uk \\ //
  51. /\__/ "I'm the boy without a soul."  \X/ 
  52.