CODEWITHSUNDEEP
pythonrecursionnested-lists
Apparent
Apparent

Reputation: 95

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

This is what I have done as of right now,

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

but when I print(unique([ 2, 1, 4, [ 3, [3, 4], 2 ], [2, 5, 6], 4, [ 2, 1 ]]))

the result is {1, 2, 4}. I'm trying to figure out why the recursion is not picking up the 5 and the 6 in that nested list? I'm just trying to grasp the recursion concept and it's difficult at first. Thanks in advance!

Upvotes: 0

Views: 113

Answers (4)

Mark Saving
Mark Saving

Reputation: 1797

A rather elegant way to do this is separating the flattening from the set-making.

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

This isn't the most efficient way to flatten the nested list. If we have a list of n elements nested n layers deep, it will take O(n^2) time to flatten it. For faster flattening, we must be cleverer.

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

This solution will be linear in the total amount of space, assuming that the reference graph forms a tree.

Upvotes: 0

Cory Kramer
Cory Kramer

Reputation: 117951

You can recursively set.union when you encounter sublists

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}

In your current implementation you call unique(item) but then do not use the result of that recursive call, so the result that gets returned is discarded and not accumulated with the current set of items.

Upvotes: 1

wjandrea
wjandrea

Reputation: 33107

You just forgot to use the recursive call to update result.

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

Output:

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

Upvotes: 1

azro
azro

Reputation: 54168

You're not using the result of unique(item), each result is local to it's method call. You need the union of the current and what is returned by the call

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}

Upvotes: 0

Related Questions