Length Sorts

Andre Roberge just informed me of a site with ninety nine Prolog problems. A quick scan and I got as far as P28 before thinking that I would like to try it. so here is my solution to P28. Note that there is much more comments than code, I decided to cut-n-paste my command line scribblings as an explanation of the second function, rather like doctests.



In doing this, I also learned that you could not take the len of a groupby object :-)



The code:


(Note: I would like to make this available under the Python License version 2.4.2)

''' \
Length sorts. From https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ P28

A code kata

Answer in Python (C) Donald 'Paddy' McCarthy,  Feb. 23, 2008
'''

from itertools import groupby


def length_sort(lst):
  ''' \
  Sort a list-of-lists on sub-list length

  Example

    >>> l = [['a','b','c'],['d','e'],['f','g','h'],['d','e'],['i','j','k','l'],['m','n'],['o']]
    >>> length_sort(l)
    [['o'], ['d', 'e'], ['d', 'e'], ['m', 'n'], ['a', 'b', 'c'], ['f', 'g', 'h'], ['i', 'j', 'k', 'l']]  
     
  '''
  return sorted(lst, key=len)

def length_freq_sort(lst):
  ''' \
  Sort a list-of-lists on frequency of sub-lists length

  Example

    >>> l = [['a','b','c'],['d','e'],['f','g','h'],['d','e'],['i','j','k','l'],['m','n'],['o']]
    >>> length_freq_sort(l)
    [['i', 'j', 'k', 'l'], ['o'], ['a', 'b', 'c'], ['f', 'g', 'h'], ['d', 'e'], ['d', 'e'], ['m', 'n']]

  '''
  ## Comments give example working out

  # >>> lst = [['a','b','c'],['d','e'],['f','g','h'],['d','e'],['i','j','k','l'],['m','n'],['o']]   
  lengths = sorted(len(x) for x in lst)
  # >>> lengths
  # [1, 2, 2, 2, 3, 3, 4]
  # >>> [(a,len(list(b))) for a,b in groupby(lengths)]
  # [(1, 1), (2, 3), (3, 2), (4, 1)]
  # >>> dict([(a,len(list(b))) for a,b in groupby(lengths)])
  # {1: 1, 2: 3, 3: 2, 4: 1}  
  len2freq = dict([(a,len(list(b))) for a,b in groupby(lengths)])

  return sorted(lst, key=lambda x: len2freq[len(x)])

Python tuples and lists

Just my attempt at explaining lists w.r.t. tuples, after href="http://news.e-scribe.com/397">this post.

With a tuple, the value and type of items at each index of a
tuple may have significance, but successive items in a tuple rarely
have similar meanings.

With lists, successive items usually have similar meanings.



(Big analogy time): cars on a motorway might be modelled as a list of
car objects, but a car might be modelled as a tuple as the constituents
of a car might be treated differently:

  style="font-family: monospace;"> style="font-weight: bold; color: rgb(255, 0, 0);">(engine,
seats, wheels, colour, valid_tax, speed,  lights_on ,... style="font-weight: bold; color: rgb(255, 0, 0);">)

 wheras each car on a motorway might be treated in a similar
way:

style="font-family: monospace;">pull_over( car for cars in style="font-weight: bold; color: rgb(255, 0, 0);">[car1,
car2, ...] if not car[valid_tax_index style="font-weight: bold; color: rgb(255, 0, 0);">])

- Paddy.