A way to re-organize a list

[Marc 'BlackJack' Rintsch]

On Wed, 01 Aug 2007 01:33:49 +0000, beginner wrote:

> On Jul 19, 10:05 am, beginner <zyzhu2... at gmail.com> wrote:
>> Hi Everyone,
>>
>> I have a simple list reconstruction problem, but I don't really know
>> how to do it.
>>
>> I have a list that looks like this:
>>
>> l=[ ("A", "a", 1), ("A", "a", 2), ("A", "a", 3), ("A", "b", 1), ("A",
>> "b", 2), ("B", "a", 1), ("B", "b", 1)]
>>
>> What I want to do is to reorganize it in groups, first by the middle
>> element of the tuple, and then by the first element. I'd like the
>> output look like this:
>>
>> out=[
>>    [    #group by first element "A"
>>           [("A", "a", 1), ("A", "a", 2), ("A", "a", 3)], #group by
>> second element "a"
>>           [ ("A", "b", 1), ("A", "b", 2)], #group by second element
>> "b"
>>    ],
>>    [   #group by first element "B"
>>           [("B", "a", 1)],
>>           [("B", "b", 1)]
>>    ]
>> ]
>>
>> All the solutions I came up with are difficult to read and even harder
>> to go back and change, and I just feel are too complicated for such a
>> simple problem. I am wondering if anyone here has some insight.
>>
>> If there is a 'functional' way to do this, it would be even greater.
>>
>> Thanks,
>> Geoffrey
> 
> I guess I still don't quite get functional programming. Here is my
> imperitive way to do it in O(n).

I didn't try to follow it but are you sure about O(n)?  With the inner
loop going from 0 to `level` it looks suspiciously quadratic to me.  You
really should try to grasp the `itertools.groupby()` solution.

And the result of that script looks strange:

[[[[1, 2, 3, 4], [1, 2, 4, 5], [1, 2, 'A', 'B']]], [[[2, 2, 'A', 'C']]]]

Aren't the two top level elements wrapped in one list too much? 
Furthermore the test data doesn't contain an example where the first item
is the same but the second item is different.

> def group_items(source_list, f_list, target=[]):

Default arguments are evaluated *once* when the ``def`` is executed.  So
all calls to this function share the same list object bound to `target`. 
Call this function twice without an explicit `target` and you'll see the
problem.

Ciao,
	Marc 'BlackJack' Rintsch