List of Lists in python?

Question

I need a good function to do this in python.

def foo(n):
    # do somthing
    return list_of_lists

>> foo(6)
   [[1],
    [2,3],
    [4,5,6]]
>> foot(10)
    [[1],
    [2,3],
    [4,5,6]
    [7,8,9,10]]

NOTE:Seems like my brain has stopped functioning today.

Answer 1

def foo(n):
  lol = [ [] ]
  i = 1
  for x in range(n):
    if len(lol[-1]) >= i:
      i += 1
      lol.append([])
    lol[-1].append(x)
  return lol

Answer 2

def foo(n):
    i = 1
    while i <= n:
        last = int(i * 1.5 + 1)
        yield range(i, last)
        i = last

list(foo(3))

What behavior do you expect when you use a number for n that doesn't work, like 9?

Answer 3

One more, just for fun:

def lol(n):
    entries = range(1,n+1)
    i, out = 1, []
    while len(entries) > i:
        out.append( [entries.pop(0) for x in xrange(i)] )
        i += 1
    return out + [entries]

(This doesn't rely on the underlying list having the numbers 1..n)

Answer 4

Adapted from gs's answer but without the mysterious "1.5".

def foo(n):
    i = c = 1
    while i <= n:
        yield range(i, i + c)
        i += c
        c += 1

list(foo(10))

Answer 5

This is probably not a case where list comprehensions are appropriate, but I don't care!

from math import ceil, sqrt, max

def tri(n):
    return n*(n+1)/2

def irt(x):
    return int(ceil((-1 + sqrt(1 + 8*x)) / 2))

def foo(n)
    [list(range(tri(i)+1, min(tri(i+1)+1, n+1))) for i in range(irt(n))]

Answer 6

Here's my python golf entry:

>>> def foo(n):
...     def lower(i): return 1 + (i*(i-1)) // 2
...     def upper(i): return i + lower(i)
...     import math
...     x = (math.sqrt(1 + 8*n) - 1) // 2
...     return [list(range(lower(i), upper(i))) for i in  range(1, x+1)]
...
>>>
>>> for i in [1,3,6,10,15]:
...     print i, foo(i)
...
1 [[1]]
3 [[1], [2, 3]]
6 [[1], [2, 3], [4, 5, 6]]
10 [[1], [2, 3], [4, 5, 6], [7, 8, 9, 10]]
15 [[1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15]]
>>>

The calculation of x relies on solution of the quadratic equation with positive roots for

0 = y*y + y - 2*n