Recursive and random grouping a list

Question

I'm trying to write a function which creates dichotomously grouped list, f. ex. if my input is as following:

[a, b, c, d, e, f, g, h]

I want to choose random integer which will split it into smaller sublists again and again recursively until the sublists' length is maximum two, like:

[[a, [b, c]], [d, [[e, f], [g, h]]]]

This is what I've got so far but still gives me TypeError(list indices must be integers or slices, not list):

def split_list(l):
    if l.__len__() > 2:
        pivot = np.random.random_integers(0, l.__len__() - 1)
        print(pivot, l)
        l = [RandomTree.split_list(l[:pivot])][RandomTree.split_list(l[pivot:])]
    return l

I got stuck and I would be very thankful for any advice.

Answer 1

Your question isn't very clear about the datatypes used and seems to use a kinda non-traditional type of recursion (probably as a part of a class). For the error scroll down a bit.

I took the liberty to alter the code a bit and use the normal random library, so what you are looking for could look like

import random # at the module-declaration part of your program

def split_list (l):
    if len(l) < 2:
        return l
    pivot = random.randint(1, len(l) - 1)
    return [RandomTree.split_list(l[:pivot]) + RandomTree.split_list(l[pivot:])]

We are halting the recursion on a single element list, and applying the recursion further if we hadn't stopped yet, using a random index pulled of the possible range (note that random.randint generates an index with the specified boundaries included).

---

Your error is not using any concatention operator between the two parts of the return value.

[A][B] does not concatenate both lists, but rather tries to index the list given in B (in your case) from A, which is a type-ly wrong usage.

Therefore you can resort to the original function (with the deprecated numpy random) as

def split_list(l):
    if l.__len__() > 2:
        pivot = np.random.random_integers(0, l.__len__() - 1)
        l = [RandomTree.split_list(l[:pivot])] + [RandomTree.split_list(l[pivot:])]
    return l

Answer 2

Here's a solution that will not make one-element lists, as per your example:

import random

def splitlist(l, minlen=2):
    if len(l) <= minlen:  # if the list is 2 or smaller,
        return l if len(l) > 1 else l[0]  # return the list, or its only element
    x = random.randint(1, len(l)-1)  # choose a random split
    return [splitlist(l[:x], minlen), splitlist(l[x:], minlen)]

Usage example:

>>> splitlist(list(range(8)))
[[0, [1, [2, [3, 4]]]], [[5, 6], 7]]