递归和随机分组列表

Question

我正在尝试编写一个创建二分组列表的函数f.恩.如果我的输入如下:

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

我想选择随机整数,它会再次递归地将它分成较小的子列表,直到子列表的长度最大为2,如:

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

这是我到目前为止所得到的但仍然给我TypeError(列表索引必须是整数或切片,而不是列表):

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

我被卡住了,我会非常感谢任何建议.

Answer 1

您的问题并不十分清楚所使用的数据类型,并且似乎使用了一种非传统类型的递归(可能作为类的一部分).对于错误向下滚动一点.

我冒昧地改变了代码并使用普通random库,所以你要找的东西看起来像

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:])]

我们正在暂停单个元素列表上的递归,并且如果我们还没有停止,则使用随机索引拉出可能的范围来进一步应用递归(注意,random.randint生成包含指定边界的索引).

您的错误不是在返回值的两个部分之间使用任何连接运算符.

[A][B]不会连接两个列表,而是尝试索引B(在您的情况下)给出的列表A,这是一种类型错误的用法.

因此,您可以使用原始函数(使用已弃用的numpy随机函数)作为

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

根据您的示例，这是一种不会创建单元素列表的解决方案：

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)]

使用示例：

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