Transform a flat list to nested List

Question

Using Python

I want the following:

[1, 2, 2, 1, 2, 3, 2, 3]

To be transformed into:

[1, 2, 2, [1, 2, 3], 2, 3]

Rules: Go through each item in the list. If we hit a 2 followed by a 1 created a list and include that 1 in that list until we hit a 3, include that 3, then close the list and continue. It's like if 1 was 3 were parenthesis.

I'm not very good with recursive algorithms which I think might be needed in this case.

Thanks as always.

Answer 1

That is an entertaining problem! Here is my solution:

def treeize(treeizable, tree=None, stopper=object()):
    if tree is None:
        tree = []

    if treeizable[:1] == [stopper]:
        tree.append(treeizable.pop(0))       
        return tree
    elif treeizable[0:2] == [2, 1]:
        tree.append(treeizable.pop(0))
        subtree = []
        treeize(treeizable, subtree, stopper=3)
        tree.append(subtree)
        return treeize(treeizable, tree, stopper)
    elif treeizable:
        tree.append(treeizable.pop(0))
        return treeize(treeizable, tree, stopper)
    else:
        return tree

This function receives a flat list treeizable that should be converted to a nested list tree. The stopper parameter marks when the current list is done - being this a nested or the toplevel list. (Since the default value of stopper is an instance of object, it is impossible that there will be a stopper on a list called with the default value, because instances of object are different between themselves).

def treeize(treeizable, tree=None, stopper=object()):

For easing our work, the default value of tree is None and, if it has the default value, then it is set to a list. It is made because it is problematic to have mutable values as default parameter objects. Also, it would be annoying to have to type the function with an empty list everytime.

    if tree is None:
        tree = []

If the first value of the flat list is the "stopper", then it is added to the tree and the tree is returned. Note that, by using treeizable.pop(0) I am actually removing the value from the flat list. Since the stopper is only set when defining a nested list so, when we found it, no more need to be done: the "subtree" (that is, the nested list) is complete. Also, note that I get the first element of the list with a slice of the list. I made it because it is boring to have to type if treeizable and treeizable[0] == stopper. Since slicing does not have problems with inexistent indexes, I got the slice and compared it to another list made in place with only the stopper:

    if treeizable[:1] == [stopper]:
        tree.append(treeizable.pop(0))       
        return tree

If the beginning of the list is the "beginner", then I pop the first element from the list, append it to the tree and create a new tree - that is, a empty list. Now I call treeize() with the remaining list and the empty subtree, also passing 3 as the stopper value. treeize() will recursively generate a new tree that I append to my initial tree. After that, just call treeize() with the remaining of the list (which does not contain the elements of the subtree anymore) and the original list. Note that the stopper should be the same stopper received by the original call.

    elif treeizable[0:2] == [2, 1]:
        tree.append(treeizable.pop(0))
        subtree = []
        treeize(treeizable, subtree, stopper=3)
        tree.append(subtree)
        return treeize(treeizable, tree, stopper)

If none of the previous conditions (the first element is a stopper, the beginning of the list is [2, 1]) is true, then I verify if there is something in the list. In this case, I pop the first element, add to the tree and call treeize() with the rest of the list.

    elif treeizable:
        tree.append(treeizable.pop(0))
        return treeize(treeizable, tree, stopper)

In the case that not even the previous condition is true... then we have an empty list. This means that all elements were put in the tree. Just return the tree to the user:

    else:
        return tree

This seems to have worked:

>>> treeize.treeize([1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 3, 2, 4, 5, 3,  3, 2, 3, 4])
[1, 2, 2, [1, 2, 2, [1, 2, 2, [1, 2, 3], 2, 4, 5, 3], 3], 2, 3, 4]

Your question has a taste of homework. In principle, we should not answer it but it is so interesting that I couldn't help myself :) If it is a homework, however, do not try to use this solution as your because it would be wrong and your teacher would surely find it on Google :P

Answer 2

Pease bear with me - it is 2:50(night) - here is my version - not very beatiful but it works pretty well for me:

def buildNewList(inputList):
    last = 0
    res = []
    for i,c in enumerate(inputList):
        if i == 0:
            prev = c
        if i < last:
            continue
        if c == 1 and prev == 2:
            if 3 in inputList[i:]:
                last = i + 1 + inputList[i:].index(3)
                res.append(buildNewList(inputList[i: last]))
            else:
                last = len(inputList)
                res.append(buildNewList(inputList[i:len(inputList)]))
        else:
            res.append(c)
        prev = c
    return res


l1 = buildNewList([1, 2, 2, 1, 2, 3, 2, 3])
>>> [1, 2, 2, [1, 2, 3], 2, 3]

l2 = buildNewList([1, 2, 2, 1, 2, 3, 2, 1, 2, 3])
>>> [1, 2, 2, [1, 2, 3], 2, [1, 2, 3]]

l3 = buildNewList([1,2,3,1,2,3])
>>> [1, 2, 3, 1, 2, 3]

l4 = buildNewList([1,2,1,1,2,1])
>>> [1, 2, [1, 1, 2, [1]]]

Answer 3

I like state machines:

from itertools import izip, tee

def pairwise(iterable):
    a, b = tee(iterable)
    next(b)
    return izip(a, b)

class Flat(object):
    def append_next(self, alist, e0, e1):
        alist.append(e0)
        if e0 == 2 and e1 == 1:
            alist.append([])
            self.__class__ = Nested
    def append_last(self, alist, e):
        alist.append(e)

class Nested(object):
    def append_next(self, alist, e0, e1):
        alist[-1].append(e0)
        if e0 == 3:
            self.__class__ = Flat
    def append_last(self, alist, e):
        alist[-1].append(e)

def nested(flat_list):
    if len(flat_list) <= 1:
        return list(flat_list)
    state = Flat()
    nested_list = []
    for x, y in pairwise(flat_list):
        state.append_next(nested_list, x, y)
    state.append_last(nested_list, y)
    return nested_list

s = [1, 2, 2, 1, 2, 3, 2, 3]

print nested(s)

gives:

[1, 2, 2, [1, 2, 3], 2, 3]

But this might be more pythonic:

def nested(flat_list):
    if len(flat_list) <= 1:
        return list(flat_list)
    pairs = pairwise(flat_list)
    nested_list = []
    while True:
        for x, y in pairs:
            nested_list.append(x)
            if x == 2 and y == 1:
                nested_list.append([])
                break
        else:
            nested_list.append(y)
            break
        for x, y in pairs:
            nested_list[-1].append(x)
            if x == 3:
                break
        else:
            nested_list[-1].append(y)
            break
    return nested_list

Answer 4

def whatever(a):
    b = []
    tmp = []
    last = None

    for elem in a:
        if tmp:
            tmp.append(elem)
            if elem == 3:
                b.append(tmp)
                tmp = []
        elif last == 2 and elem == 1:
            tmp.append(1)
        else:
            b.append(elem)
        last = elem
    return b

print whatever([1, 2, 2, 1, 2, 3, 2, 3])

Answer 5

Still keeping in mind that @Walter is correct in his comments to your question, this is a silly implementation of what you asked for, inspired by the final bit of your question, in which you suggest that 1 and 3 could just be replaced with [1 and 3].

>>> import re
>>> s = repr([1, 2, 2, 1, 2, 3, 2, 3])
>>> s = re.sub('1', '[1', s)
>>> s = re.sub('3', '3]', s)
>>> l = eval(s)
>>> l
[[1, 2, 2, [1, 2, 3], 2, 3]]

What it does is working on the representation of the list (a string) and substituting the way you suggested using regular expressions. Finally, it evaluate the string (getting back a list).

I call this implementation "silly" because it does the trick, but it's ugly and truly unpythonic. That said, it does the trick, so if you are simply using it for a one-off conversion of some data you need to use...

HTH!