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