EDIT: See below for a suggested answer and how it's not quite right yet.
There are many similar questions to this one on Stack Overflow, but none exactly like it in Python. I'm a programming novice, so please go easy.
I have a tree of nested dictionaries, like this:
[{'word': 'The',
'next': [{'word': 'End',
'next': None},
{'word': 'quick',
'next': [{'word': 'brown',
'next': [{'word': 'fox',
'next': None}]}]},
{'word': 'best',
'next': [{'word': 'of',
'next': [{'word': 'times',
'next': None}]}]}]}]
I want to flatten all paths from top to bottom and end up with this:
[[{'word': 'The'},
{'word': 'End'}],
[{'word': 'The'},
{'word': 'quick'},
{'word': 'brown'},
{'word': 'fox'}],
[{'word': 'The'},
{'word': 'best'},
{'word': 'of'},
{'word': 'times'}]]
I made a lovely little recursive function that created the original structure in the first place, but I'm having a hard time unrecursivizing it. This is as far as I got:
def flatten_combinations(result_tree, current_combo = None, all_combos = None):
if current_combo is None:
current_combo = []
if all_combos is None:
all_combos = []
if result_tree is None:
all_combos.append(current_combo)
return
for word in result_tree:
current_combo.append({'word': word['word']})
flatten_combinations(word['next'], current_combo, all_combos)
return current_combo
…which returns this:
[{'word': 'The'},
{'word': 'End'},
{'word': 'quick'},
{'word': 'brown'},
{'word': 'fox'},
{'word': 'best'},
{'word': 'of'},
{'word': 'times'}]
…which is clearly somewhat close, but not quite right.
I know that function is probably horribly un-Pythonic, but I'm teaching myself programming, so I'm not even trying to take advantage of possibly-existent language features that would let me elide over thinking through this stuff from scratch (” he said, posting to a Q&A site in the hope its members would help him elide a bit of thought).
So: what am I doing wrong?
EDIT: Moshe below corrected a couple of problems:
def flatten_combinations(result_tree, current_combo = None, all_combos = None):
if current_combo is None:
current_combo = []
if all_combos is None:
all_combos = []
if result_tree is None:
all_combos.append(current_combo)
return
for word in result_tree:
current_combo = current_combo[:]
current_combo.append({'word': word['word']})
flatten_combinations(word['next'], current_combo, all_combos)
return all_combos
This is closer yet, but not quite right:
[{'word': 'The'},
{'word': 'End'}],
[{'word': 'The'},
{'word': 'End'},
{'word': 'quick'},
{'word': 'brown'},
{'word': 'fox'}],
[{'word': 'The'},
{'word': 'End'},
{'word': 'quick'},
{'word': 'best'},
{'word': 'of'},
{'word': 'times'}]]
There are two minor mistakes in that:
1) You return current_combo
instead of all_combos
. That only gives you your last result
2) On each iteration, you modify current_combo
. Make a copy first!
new_current_combo = current_combo[:]
new_current_combo.append({'word': word['word']})
flatten_combinations(word['next'], new_current_combo, all_combos)
Full code:
def flatten_combinations(result_tree, current_combo=None, all_combos=None):
if current_combo is None:
current_combo = []
if all_combos is None:
all_combos = []
if result_tree is None:
all_combos.append(current_combo)
return
for word in result_tree:
new_current_combo = current_combo[:]
new_current_combo.append({'word': word['word']})
flatten_combinations(word['next'], new_current_combo, all_combos)
return all_combos
If you pass in a copy of current_combo on the recursive call then you won't lose your current path on the next iteration of your for loop.
Also, you don't need to return current_combo since the result isn't used in recursion. You might want to return all_combos instead and not take it as a parameter. Alternatively, you could have a recursive function and none recursive function, with the no-recursive function creating the list for all_combos and passing it into the recursive function so that the recursive function could assume all_combos was set.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With