combinations.py

# To reproduce this Haskell function in Python we need to define some helper
# functions first. But Python's list comprehensions support nested loops just
# like Haskell.
#
# combinations :: Int -> [a] -> [[a]]
# combinations 0 _  = [ [] ]
# combinations n xs = [ y:ys | y:xs' <- tails xs, ys <- combinations (n-1) xs']

def headtail(lst):
  """
  Return a pair of the first element in the list and the rest of the list.
  """
  head = lst[0]
  tail = lst[1:]
  return (head, tail)

def tails(lst):
  """
  Generator to iterate over the sublists from each starting element to the end.
  """
  for i in xrange(len(lst)):
    yield lst[i:]

def prepend(elem, lst):
  """
  Return a new list starting with elem followed by all of lst.
  """
  lst1 = lst[:] # clone
  lst1.insert(0, elem)
  return lst1

def combinations(n, xs):
  """
  Return a list containing each possible combination of n items taken from xs.
  """
  if n <= 0:
    return [[]]
  else:
    return [prepend(y, ys) for (y,xs1) in map(headtail, tails(xs)) for ys in combinations(n-1, xs1)]

if __name__ == "__main__":
  elems = ["a", "b", "c", "d", "e"]
  print combinations(1, elems) # 5 x 1 letter combinations
  print combinations(len(elems), elems) # everything, 1 combination
  print combinations(2, elems)
  print combinations(3, elems)
  print combinations(4, elems)