0

我正在尝试制作自己的八叉树版本，如果您尝试添加不同大小的点，则会遇到问题，因为降低深度级别只会覆盖所有内容，因此会删除较大块上的任何信息。

我认为解决此问题的最佳方法是向后检查最后一点，并将列表重建到新点的深度。但是，我实际上无法弄清楚如何构建列表，尽管事实上很容易想到我所追求的输出。

这是使用示例开始和结束列表构建列表所需的数据，我需要它的格式为["Nodes",(coordinate),"Nodes",(coordinate)...]每个坐标覆盖structure列表中的每个项目，直到它到达末尾。

structure = [(-1, -1, -1), (-1, -1, 1), (-1, 1, -1), (-1, 1, 1), (1, -1, -1), (1, -1, 1), (1, 1, -1), (1, 1, 1)]

start = ['Nodes', (1, 1, 1), 'Nodes', (-1, -1, -1)]
end = ['Nodes', (1, 1, 1), 'Nodes', (-1, -1, -1), 'Nodes', (1, 1, 1), 'Nodes', (-1, -1, -1), 'Nodes', (1, -1, -1), 'Nodes', (-1, -1, -1)]
length = len( end )-len( start )

这是一个极端的例子（从深度 4 到 0），会产生 4096 个不同的值，尽管 99% 的情况下它不会有这么大，所以性能应该不太重要。

在示例开始值和结束值的情况下，我不需要每个长度的值，它们只需要最大长度，就像这样 -

['Nodes', (1, 1, 1), 'Nodes', (-1, -1, -1), 'Nodes', (-1, -1, -1), 'Nodes', (-1, -1, -1), 'Nodes', (-1, -1, -1), 'Nodes', (-1, -1, -1)]
['Nodes', (1, 1, 1), 'Nodes', (-1, -1, -1), 'Nodes', (-1, -1, 1), 'Nodes', (-1, -1, -1), 'Nodes', (-1, -1, -1), 'Nodes', (-1, -1, -1)]
['Nodes', (1, 1, 1), 'Nodes', (-1, -1, -1), 'Nodes', (-1, 1, -1), 'Nodes', (-1, -1, -1), 'Nodes', (-1, -1, -1), 'Nodes', (-1, -1, -1)]
#4002 values later
['Nodes', (1, 1, 1), 'Nodes', (-1, -1, -1), 'Nodes', (1, 1, 1), 'Nodes', (1, 1, 1), 'Nodes', (1, 1, 1), 'Nodes', (1, 1, 1)]

我有过尝试，但在它实际上不是递归之后我意识到，无论如何，它就是 -

newThing = {}
for i in range( length/2 ):
    try:
        #Set it to previous level so you can append
        newThing[i] = newThing[i-1]
    except:
        #Start off the dictionary
        newThing[i] = {}
        for j in range( len( structure ) ):
            newThing[i][j] = start
    #Add structure value for each one
    for j in range( len( structure ) ):
        newThing[i][j].append( "Nodes" )
        newThing[i][j].append( structure[j] )

我真正需要的是运行时的每个列表，所以如果它可以到达一个可以从循环内打印所有组合的阶段，那就太好了，因为存储所有这些组合不会浪费内存:)

4

1 回答 1

0

由于没有人回答，我认为绕过它的最简单方法是递归函数，并且很幸运。它将继续构建列表，直到达到最大长度，并立即将它们全部返回。

def recursiveList( currentInput, combinations, length ):
    newInputList = []
    for input in currentInput:
        if len( input ) < length:
            for combination in combinations:
                newInputList += recursiveList( [input + [input[0], combination]], combinations, length )
        else:
            newInputList.append( input )
    return newInputList

使用我在问题中发布的值，recursiveList( [start], structure, len(end) )将返回 4096 个正确值

它比我想象的要快得多，这是 timeit 结果 -

64 个列表：0.0000057 秒
512 个列表：0.00048 秒
4096 个列表：0.004 秒
32768 个列表：0.032 秒

于 2015-03-17T02:05:32.787 回答