Source
r/learnpython•
Supercluster

List into 2d List - "Triangle"

This is simple but I cannot figure out an elegant way to do this...

list = [1,2,3,4,5,6,7,8,9,10]
triangle = [[1],[2,3],[4,5,6],[7,8,9,10]]

What shape of loop is required to get from 'list' to 'triangle'. Assuming I want to do it to a list with thousands of values...

Posted Apr 2, 2013, 3:01 PM UTC

76
DangerousDuck•

Let's take it step by step. What do we want? A list of slice of the original list with the slice length increasing by 1 for each iteration. Recursion is always fun for such problems.

def triangle(l, i = 1):
    return [] if len(l) < i else [l[: i]] + triangle(l[i:], i + 1)

[] if len(l) < i

The base case is when the slice lent is greater then the list lenght, so we return an empty list if the index is out of bounds.

Next we take the actual slice.

[l[:i]]

We slice of the list by slicing a length i of the start of the list. To this we add the resulting list of the recursive call we will be doing next.

triangle(l[i:], i + 1)

We pass two arguments to the recursive call. First the new list with the front sliced off, next the new slice length.

Some notes about this implementation. Recursion is not always the fastest way in python, so for more performance you might want to change it into a regular loop. For me this gave reasonable speed up to a list of 100,000 values.

Also, in this example I cut-off all the values not fitting in the triangle. If you don't like this simple change the base case to [l] if len(l) < i to add the rest of the list to the end.

2
SuperclusterOP•

This works perfectly. I will try and study it further to understand it fully. And possibly try a method which doesn't involve the recursive function ( just for practice)...

1
[deleted]•

Here's a regular loop. In each pass you're adding a slice of the source list to the destination list, the starting index for the subsequent slice increases by the length, and the length for the subsequent slice increases by one. When the index reaches the end of the source list, the loop stops.

source = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
destination = []

index = 0
length = 1

while index < len(source):
    destination.append(source[index : index + length])
    index += length
    length += 1

print(destination)

Here's a generator which accomplishes the same thing.

def triangle_blocks(s):
    i,L = 0,1
    while i < len(s):
        yield s[i : i+L]
        i += L; L += 1

s = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
d = list(triangle_blocks(s))

print(d)
3
MonkeyNinninmonkey•

Are you asking about a tree structure? http://en.wikipedia.org/wiki/Tree_%28data_structure%29

2
toodim•

Are you doing this for Project Euler by chance? I was just working on the triangle path sums problems yesterday.

1
SuperclusterOP•

Yes indeed.

1