home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / misc / 3287 < prev    next >
Encoding:
Internet Message Format  |  1992-08-21  |  1.4 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!ucbvax!amex-trs.com!gonzalod
  2. From: gonzalod@amex-trs.com (Gonzalo Diethelm)
  3. Newsgroups: comp.misc
  4. Subject: Generic sorting functions
  5. Message-ID: <9208212151.AA38407@cs90code.csv-tgsc.amex-trs.com>
  6. Date: 21 Aug 92 21:51:31 GMT
  7. Sender: daemon@ucbvax.BERKELEY.EDU
  8. Lines: 42
  9.  
  10.  
  11.  
  12. Distribution: world
  13.  
  14. Hello everyone,
  15.  
  16. A very generic question. Given a set S of n strings (the `|' characters
  17. are used as delimiters):
  18.  
  19.   s1   |dunno|
  20.   s2   |I'd rather have a bottle in front of me than a frontal lobotomy|
  21.   s3   |eschew clever rules|
  22.   ... ...
  23.   sn   |bzzzzt!|
  24.  
  25. and an ordering sequence O:
  26.  
  27.   {s4, s1, s6, s2, sn, s3, ... s7}
  28.  
  29. is there any way to determine a fixed, hopefully cheap function
  30.  
  31.   f(): SxS -> integers
  32.  
  33. with the property that
  34.  
  35.   if si comes before sj in O, f(si, sj) < 0
  36.   if si comes after  sj in O, f(si, sj) > 0
  37.  
  38. that is, could be used to sort the strings in the given sequence?
  39. For example, if the desired sequence happens to be the alphabetical
  40. descending ordering of the strings, f() could just be
  41.  
  42.   f = -1 * strcmp(si, sj);
  43.  
  44. My intuiton tells me this is possible, but I don't really know how
  45. to approach the problem. Any help is welcome. Please send answers
  46. and flames via e-mail. Thanks in advance and kindest regards.
  47.  
  48. gonzalod@amexphx.amex-trs.com
  49. Gonzalo A. Diethelm                 (602)375-8410  home
  50. 16220 N 7th St Ap 1314              (602)492-3536  office
  51. Phoenix, AZ 85022                   (602)492-4248  FAX
  52.