Rhyming Sort

December 8, 2020

I recently found on the internet a delightful paper by Kenneth Ward Church called Unix™ for Poets that provides an introduction to the Unix command line utilities for text processing. The paper must be ancient, because it gives the author’s email address at research.att.com, but I’ve never seen it before. One of the examples in the paper is rhyming sort, in which words are sorted from the right rather than the left; the left column below is in normal alphabetical order, the right column is in rhyming order:

    falsely         freely
    fly             sorely
    freely          surely
    sorely          falsely
    surely          fly

Church says:

“freely” comes before “sorely” because “yleerf” (“freely” spelled backwards) comes before “yleros” (“sorely” spelled backwards) in lexicographic order. Rhyming dictionaries are often used to help poets (and linguists who are interested in morphology).

Church solved the problem with a rev | sort | rev pipeline.

Your task is to sort a file containing one word per line into rhyming order. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

4 Responses to “Rhyming Sort”

  1. chaw said

    Here is a “one-liner” using standard R7RS Scheme and a couple of well
    known helpers that seems very close in spirit to the Unix pipeline
    solution. In comparing it to the solution by @programmingpraxis, one
    difference is that this one makes only Theta(n) string-reversals
    instead of Theta(n log n). Based on some very quick tests on larger
    inputs (e.g., /usr/share/dict/words on Debian GNU/Linux), the
    difference can be quite significant (10x).

    (import (scheme base)
            (scheme write)
            (only (srfi 13) string-reverse)
            (only (srfi 132) list-sort))
    (define sample '("falsely" "fly" "freely" "sorely" "surely"))
    (define (rhyming-sort strs)
      (map string-reverse (list-sort string<? (map string-reverse strs))))
    (display sample)
    (display (rhyming-sort sample))


    (falsely fly freely sorely surely)
    (freely sorely surely falsely fly)

  2. matthew said

    We might as well use some actual poetry for our test data, so here is some Chaucer. After sanitizing the text, reverse all words, sort with appropriate collation (to get, for example, ‘vertú’ in the right place – Unicode combining characters might be a problem), and reverse again before final output:

    import locale
    s = """
    Whan that Aprille with his shoures soote,
    The droghte of March hath perced to the roote,
    And bathed every veyne in swich licóur
    Of which vertú engendred is the flour;
    Whan Zephirus eek with his swete breeth
    Inspired hath in every holt and heeth
    The tendre croppes, and the yonge sonne
    Hath in the Ram his halfe cours y-ronne,
    And smale foweles maken melodye,
    That slepen al the nyght with open ye,
    So priketh hem Natúre in hir corages,
    Thanne longen folk to goon on pilgrimages,
    And palmeres for to seken straunge strondes,
    To ferne halwes, kowthe in sondry londes;
    And specially, from every shires ende
    Of Engelond, to Caunterbury they wende,
    The hooly blisful martir for to seke,
    That hem hath holpen whan that they were seeke.
    words = set(w.rstrip(';,.')[-1::-1] for w in s.lower().split())
    print(" ".join(s[-1::-1] for s in sorted(words, key=locale.strxfrm)))
    # perced bathed engendred inspired and engelond ende wende halfe yonge
    # straunge the kowthe seeke seke smale aprille thanne y-ronne sonne
    # ferne veyne tendre were natúre swete droghte roote soote ye melodye
    # of which swich march hath heeth breeth priketh with eek folk al
    # blisful ram hem from whan longen maken seken slepen holpen open in
    # on goon so to hir martir for licóur flour londes strondes
    # pilgrimages corages foweles croppes palmeres shires shoures halwes
    # is his cours zephirus that nyght holt vertú they specially hooly
    # sondry every caunterbury
  3. Steve said


            str::["falsely" "fly" "freely" "sorely" "surely"]
    ["falsely" "fly" "freely" "sorely" "surely"]
    ["freely" "sorely" "surely" "falsely" "fly"]

    Adopting Chaucer’s sample text (Thanks, @matthew), I get the following:

    ["whan" "that" "aprille" "with" "his" "shoures" "soote" "the" "droghte" "of" "march" "hath" "perced" "to" "the" "roote" "and" "bathed" "every" "veyne" "in" "swich" "licóur" "of" "which" "ertú" "engendred" "is" "the" "flour" "whan" "zephirus" "eek" "with" "his" "swete" "breeth" "inspired" "hath" "in" "every" "holt" "and" "heeth" "the" "tendre" "croppes" "and" "the" "yonge" "sonne" "hath" "in" "the" "ram" "his" "halfe" "cours" "y-ronne" "and" "smale" "foweles" "maken" "melodye" "that" "slepen" "al" "the" "nyght" "with" "open" "ye" "So" "priketh" "hem" "natúre" "in" "hir" "corages" "thanne" "longen" "folk" "to" "goon" "on" "pilgrimages" "and" "palmeres" "for" "to" "seken" "straunge" "strondes" "to" "ferne" "halwes" "kowthe" "in" "sondry" "londes" "and" "specially" "from" "every" "shires" "ende" "of" "engelond" "to" "caunterbury" "they" "wende" "the" "hooly" "blisful" "martir" "for" "to" "seke" "that" "hem" "hath" "holpen" "whan" "that" "they" "were" "seeke"]
    ["perced" "bathed" "engendred" "inspired" "and" "engelond" "ende" "wende" "halfe" "yonge" "straunge" "the" "kowthe" "seeke" "seke" "smale" "aprille" "thanne" "y-ronne" "sonne" "ferne" "veyne" "tendre" "were" "natúre" "swete" "droghte" "roote" "soote" "ye" "melodye" "of" "which" "swich" "march" "hath" "heeth" "breeth" "priketh" "with" "eek" "folk" "al" "blisful" "ram" "hem" "from" "whan" "longen" "maken" "seken" "slepen" "holpen" "open" "in" "on" "goon" "So" "to" "hir" "martir" "for" "flour" "licóur" "londes" "strondes" "pilgrimages" "corages" "foweles" "croppes" "palmeres" "shires" "shoures" "halwes" "is" "his" "cours" "zephirus" "that" "nyght" "holt" "they" "specially" "hooly" "sondry" "every" "caunterbury" "ertú"]
  4. lisper said

    A common lisp solution.

    (defun read-file-into-list (file-path)
      "return an ordered list of strings of each line in file-path"
      (with-open-file (in file-path)
          for line = (read-line in nil)
           while line collect line)))
    (defun rhyming-sort (data-list)
      (sort data-list #'(λ (s u) (string-lessp (reverse s) (reverse u)))))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: