python:如何对单层嵌套列表快速生成相邻子序列

Linius 发布于 2012/04/27 21:12
阅读 960
收藏 0
如何对单层嵌套列表快速生成相邻子序列?例如[[1,11,111],[2,22,222],[3],[4,44]]生成相邻子序列:[1], [1,2], [1,22], [1,222], [1,2,3], [1,22,3], [1,222,3], [1,2,3,4], [1,22,3,4], ... , [2, 3], [2, 3, 4], [2,3,44]...等

以下是问题补充:

@Linius:要求使用尽可能高效的算法 (2012/04/27 21:14)
加载中
1
刘地
刘地
def UnwrapIt(lst):
	if type(lst)==type([]):
		sub=[]
		for i in lst:sub.extend(UnwrapIt(i))
		return sub
	elif type(lst)==type(()):
		return [tuple(UnwrapIt(list(lst))),]
	else:
		return [lst,]
	pass
0
Linius
Linius
自己实现了一种简易的算法,如下。这种算法使用递归以及生成器的思想。由于当嵌套子序列长度过大时,程序运行消耗的内存过多,故只输出子序列长度小于5的结果。
# -*- coding: gbk -*-

def func(k):
    a = range(len(k))
    bb = func1(a)
    for b in bb:
        if len(b) < 5:
            yield func2(b, k)
    
def func1(a):
    '''
    对嵌套列表的序号生成相邻子序列,例如:
    k = [[1,11],[2,22,222],[3]]对应序号[0,1,2],
    生成的相邻子序列为:bb = [[0],[0,1],[0,2],[1],[1,2],[2]]
    '''
    result = []
    length = len(a)
    for i in xrange(length):
        for j in xrange(i + 1, length + 1):
            result.append(a[i:j])
    return result

def func2(b, k):
    '''
    将b序列中的值对应k中的子序列序号,
    并逐步使用k中对应子序列中的值进行替换.
    例如for b in bb, b中0对应着k中[1,11],
    1对应着[2,22,222],依此类推
    '''
    result = []
    if len(b) == 1:
        for i in k[b[0]]:
            result.append([i])            
    else:
        temp = func2(b[1:], k)
        for j in k[b[0]]:
            for jj in temp:
                result.append([j] + jj)
    return result
    

OSCHINA
登录后可查看更多优质内容
返回顶部
顶部