Optimize algorithm to work with tuples, sets and dictionarys

Question

I have a list flattening algorithm:

def flatten(s):
    if not s:
        return s
    if isinstance(s[0], (list, set, tuple)):
        return flatten(s[0]) + flatten(s[1:])
    return s[:1] + flatten(s[1:])

But it doesn't work if you combine two different data types. A list inside a tuple for example. Is there a way to do this? Also would flattening dicts be possible? The values, not the keys.

what exactly do you mean by 'flattening'? Sample input and output would be useful — Jonathan S, Oct 01 '19 at 11:26
This answer uses itertools.chain() : https://stackoverflow.com/a/953097/509840. Here's the documentation for Python 3.7: https://docs.python.org/3.7/library/itertools.html#itertools.chain — rajah9, Oct 01 '19 at 11:31

ksha · Answer 1 · 2019-10-01T13:41:05.207

3

Using itertools -> chain or standard libraries is usually recommended, but for arbitrarily nested containers:

xlen = len(x)
result = []    

def flatten(x, i, xlen, result):
  if i >= xlen:
    return
  if not isinstance(x[i], (list, set, tuple)):
    result.append(x[i])
  else:
    flatten(list(x[i]), 0, len(x[i]), result)
  flatten(x, i+1, xlen, result)

you can add corner cases for empty containers, etc.

edited Oct 01 '19 at 13:41

answered Oct 01 '19 at 11:40

ksha

2,007
1
19
22

For arbitrarily deep flattening, you show me pls how you can get rid of recursion using `itertools.chain`. – user2390182 Oct 01 '19 at 11:59
Updated the answer, but you know I can mix chain and recursion to win an argument :) – ksha Oct 01 '19 at 13:03

score 2 · Answer 2 · answered Oct 01 '19 at 11:56

There are several algorithms on SO to flatten nested lists and tuples, but we will stick with yours. The first observation is that your algorithm as written will not work with set instances since they are not subscriptable. So sets have to go:

def flatten(s):
    if not s:
        return s
    if isinstance(s[0], (list, tuple)):
        return list(flatten(s[0])) + list(flatten(s[1:]))
    return list(s[:1]) + list(flatten(s[1:]))

flatten([[1,2,(3,4,(5,6))]])

Prints:

[1, 2, 3, 4, 5, 6]

Thanks, this is really helpful. All of the answers here work! — , Oct 08 '19 at 10:21

score 1 · Answer 3 · answered Oct 01 '19 at 12:49

If you are looking for optimization and some fun ... Recursion is okey, but don't forget about RecursionError.

Input:

from datetime import datetime
from typing import Sequence


def timer(f):
    def wrapped(s):
        start = datetime.now()
        result = f(s)
        print(datetime.now() - start)
        return result
    return wrapped


@timer
def str_method(s: Sequence):
    return [int(x) for x in
            str(s).replace("(", "[").replace(")", "]")[1:-1].replace("[", "").replace("]", "")
            if x not in [",", " "]]


def flatten(s: Sequence):
    if not s:
        return s
    if isinstance(s[0], (list, tuple)):
        return list(flatten(s[0])) + list(flatten(s[1:]))
    return list(s[:1]) + list(flatten(s[1:]))

if __name__ == '__main__':
    s = [1, 2, (3, 4, (5, 6))]
    start = datetime.now()
    print(flatten(s))
    print(datetime.now() - start)
    print(str_method(s))
    print("-")
    s = [(x, ) for x in range(100)]
    start = datetime.now()
    flatten(s)
    print(datetime.now() - start)
    str_method(s)
    print("-")
    s = [(x, ) for x in range(100000)]
    start = datetime.now()
    try:
        print(flatten(s))
    except RecursionError:
        print("RecursionError")
    str_method(s)

Output:

[1, 2, 3, 4, 5, 6]
0:00:00.000022 # flatten
0:00:00.000041 # str_method
[1, 2, 3, 4, 5, 6]
-
0:00:00.000369 # flatten
0:00:00.000122 # str_method
-
RecursionError # flatten
0:00:00.186894 # str_method

score 0 · Accepted Answer · answered Oct 02 '19 at 23:17

0

The other answers are all valid, but if you are importing sympy into your code, maybe use it's flatten method? It's very fast, and suits your needs.

answered Oct 02 '19 at 23:17

Legorooj

2,646
2
15
35

I've selected this answer only because i actually happen to by using sympy! What are the chances? – Oct 08 '19 at 10:20

Optimize algorithm to work with tuples, sets and dictionarys

4 Answers4