Convert from tuple of tuples to nested tuples in Python

Question

Is there a simple way to convert

t = ((1,), (1, 2), (1, 2, 3), (1, 2, 3, 4), (1, 2, 3, 4, 5))

to the following recursive structure, where each following tuple is appended as an element of the prior tuple

(1, (1, 2, (1, 2, 3, (1, 2, 3, 4, (1, 2, 3, 4, 5)))))

What is the limit to this nesting? Can I have a 1000 or 10000 such nested tuples?

UPDATE: It seems t nesting is unlimited (tried with 10000 after setting recursion limit to 100).

On Window 7, Python 3.5) the recursion limit is around 300 at first, but can be lifted as (reference). This is not related to structure t, but may be related to Python routine accessing nested levels of the resulting structure.

sys.getrecursionlimit()   # display current recursion level
sys.setrecursionlimit(10000)  # set recursion level to 1000

The recursion limit you have mentioned is related to the nember stack frames we can use, i.e. it's about how deeply recursive function calls can go. It's completely unrelated to how deeply you can nest tuples like this, which I expect is unbounded (except by available memory). — wim, Nov 18 '15 at 17:39
Great note! I updated the question. I do, however, run into recursion limit issue when I run David's code and display `result`. See my comment to David. — Oleg Melnikov, Nov 18 '15 at 18:39

falsetru · Answer 1 · 2015-11-18T23:07:34.637

6

Using functools.reduce:

>>> from functools import reduce
>>> t = ((1,), (1, 2), (1, 2, 3), (1, 2, 3, 4), (1, 2, 3, 4, 5))
>>> reduce(lambda a, b: b + (a,), reversed(t), ())
(1, (1, 2, (1, 2, 3, (1, 2, 3, 4, (1, 2, 3, 4, 5)))))

edited Nov 18 '15 at 23:07

answered Nov 18 '15 at 02:53

falsetru

357,413
63
732
636

2

I was waiting for the reduce answer. One of the few times when reduce actually *is* appropriate. – wim Nov 18 '15 at 02:54
Great solution. Thanks! – Oleg Melnikov Nov 18 '15 at 06:45
1

@EmilyHill, FYI, the accept answer will not work with empty tuple. – falsetru Nov 18 '15 at 06:51
Thanks for noticing. Empty tuple is not a concern. I must add that `functool` solution is fantastic as well. Too bad that only one can be accepted. – Oleg Melnikov Nov 18 '15 at 06:53
1

@EmilyHill, If it was Python 2.x, you don't need to import `reduce` from `functools` because it's a builtin function. – falsetru Nov 18 '15 at 07:10
Thanks a bunch. This is for Python 3.x :) – Oleg Melnikov Nov 18 '15 at 07:16
1

@falsetru Your answer doesn't work with an empty tuple either; indeed, it's not even clear what the output should be (`None`?). – David Eisenstat Nov 18 '15 at 19:21
@DavidEisenstat, Thank you for your feedback. I updated the answer to work with empty tuple. I think an empty tuple should be returned. – falsetru Nov 18 '15 at 23:08

score 0 · Answer 2 · answered Nov 18 '15 at 02:49

For the nested construction:

def f(t):
    res = t[-1]
    for x in t[-2::-1]:
        res = x + (res,)
    return res

t = ((1,), (1, 2), (1, 2, 3), (1, 2, 3, 4), (1, 2, 3, 4, 5))
print f(t)

for how big it can be, I don't know but I would assume it depends on your machine, your settings and so on...

score 0 · Accepted Answer · answered Nov 18 '15 at 02:50

0

You could do

def convert(t):
    result = t[-1]
    for x in t[-2::-1]:
        result = x + (result,)
    return result

which iterates backward through t. You can probably construct a very deeply nested tuple, but you might have trouble printing it out.

answered Nov 18 '15 at 02:50

David Eisenstat

64,237
7
60
120

I like your approach because its brief and doesn't use unnecessary tools. Thanks! – Oleg Melnikov Nov 18 '15 at 06:45
David, neat routine. It may benefit from a setting recursion limit to depth of `t`, otherwise it throws `RecursionError: maximum recursion depth exceeded while calling a Python object` for deeply nested `t`. Try `sys.setrecursionlimit(10)` followed by convert(tuple(tuple(range(k)) for k in range(1,20)))` – Oleg Melnikov Nov 18 '15 at 18:47
1

@EmilyHill There is no recursion in my code. The specific error is `RuntimeError: maximum recursion depth exceeded while getting the repr of a tuple`, which is the Python REPL trying and failing to print out the result, as I predicted. If you change the entered command to discard the output by appending `[:0]` (to take an empty slice), then everything works fine. – David Eisenstat Nov 18 '15 at 19:20
David, I think the recursion in your code is implied by `result = x + (result,)`. It's not an explicit recursion. It appears falsetru's solution faces the same challenge :) – Oleg Melnikov Nov 18 '15 at 19:24
@EmilyHill As I said, try `convert(tuple(tuple(range(k)) for k in range(1,20)))[:0]` with the lowered recursion limit. The error is not in my code. – David Eisenstat Nov 18 '15 at 19:39
Good point. Indeed, with a 100 recursion limit, `x=convert(tuple(tuple(range(k)) for k in range(1,200)))` executes fine, but printing `x` on screen throws an error. Thanks for clarification. – Oleg Melnikov Nov 18 '15 at 19:48

Convert from tuple of tuples to nested tuples in Python

3 Answers3