我正在编写一个函数，它将使用递归 return 嵌套列表中的一组唯一元素

Question

这是我目前所做的，

def unique(L):
    '''
    Returns set of unique elements in nested list L
    Ex.      unique([ 2, 1, 4, [ 3, [3, 4], 2 ], [2, 5, 6], 4, [ 2, 1 ]])
    returns: {1, 2, 3, 4, 5, 6}
    '''
    
    result = set()
    for item in L:
        if isinstance(item, list):
            unique(item)
        else:
            result.add(item)
    return result

但是当我 print(unique([ 2, 1, 4, [ 3, [3, 4], 2 ], [2, 5, 6], 4, [ 2, 1 ]]))

结果是{1, 2, 4}。我试图弄清楚为什么递归没有在该嵌套列表中获取 5 和 6？我只是想掌握递归概念，一开始很难。提前致谢！

Answer 1

您没有使用 unique(item) 的结果，每个 result 对于它的方法调用都是本地的。您需要当前和调用返回的内容的联合

def unique(L):
    result = set()
    for item in L:
        if isinstance(item, list):
            result = result.union(unique(item)) # with method
            # result |= unique(item)            # with operator
        else:
            result.add(item)
    return result

print(unique([2, 1, 4, [3, [3, 4], 2], [2, 5, 6], 4, [2, 1]]))  # {1, 2, 3, 4, 5, 6}

Answer 2

遇到子列表可以递归set.union

def unique(L):
    result = set()
    for item in L:
        if isinstance(item, list):
            result |= unique(item) # recurse, then union with current set
        else:
            result.add(item)
    return result

>>> unique([ 2, 1, 4, [ 3, [3, 4], 2 ], [2, 5, 6], 4, [ 2, 1 ]])
{1, 2, 3, 4, 5, 6}

在您当前的实现中，您调用 unique(item) 但随后不使用该递归调用的结果，因此返回的 result 被丢弃并且不会与当前项目集一起累积。

Answer 3

您只是忘记使用递归调用来更新 result。

...
if isinstance(item, list):
    result.update(unique(item))
...

输出：

{1, 2, 3, 4, 5, 6}

Answer 4

一个相当优雅的方法是将展平与制作分开。

def flatten(nested_list):
    if isinstance(nested_list, list):
        for x in nested_list:
            for y in flatten(x):
                yield y
    else:
        yield nested_list

def unique(nested_list):
    return set(flatten(nested_list))

这不是展平嵌套列表的最有效方式。如果我们有一个 n 元素的列表，嵌套 n 层深，则需要 O(n^2) 时间来展平它。为了更快的扁平化，我们必须更聪明。

class FlattenIterator:
    def __init__(self, nested_list):
        self.stack = [iter((nested_list,))]
    
    def __iter__(self):
        return self
    
    def __next__(self):
        while self.stack:
            top_most = self.stack[-1]
            try:
                next_item = next(top_most)
                if isinstance(next_item, list):
                    self.stack.append(iter(next_item))
                else:
                    return next_item
            except StopIteration:
                self.stack.pop()
        raise StopIteration

def unique(nested_list):
    return set(FlattenIterator(nested_list))

假设参考图形成一棵树，此解决方案将与 space 的总量成线性关系。

我正在编写一个函数，它将使用递归 return 嵌套列表中的一组唯一元素

I'm writing a function which will return a set of unique elements in a nested list using recursion

python

recursion

nested-lists