Create a recursive list from a list categories

user_3302016 0
Viewed 50

I am working on a peice of code where i have some input data in this format:

_input = [
        ('Cat 1', 'Sub Cat 1', 'lvl_3_cat-1'),
        ('Cat 1', 'Sub Cat 2', 'lvl_3_cat-2'),
        ('Cat 2', 'Sub Cat 3', 'lvl_3_cat-3')
    ]

I need to convert the following list of catefories into a parent child nested list which can be iterated to get the list of nested relations.

Expected Output

expected output = [{
    "name": 'Cat 1',
    "children": [{
        "name": 'Sub Cat 1',
        "children": [{
            "name": 'lvl_3_cat-1',
            "children": []
        }]
    },{
        "name": 'Sub Cat 2',
        "children": [{
            "name": 'lvl_3_cat-2',
            "children": []
        }]
    }]
},{
    "name": 'Cat 2',
    "children": [{
        "name": 'Sub Cat',
        "children": [{
            "name": 'lvl_3_cat-3',
            "children": []
        }]
    }]
}]

Input in this example has a 3 level nesting but this can be dynamic i.e upto n.

My current code

    def dsearch(lod, name):
        for e in lod:
            if e["name"] == name:
                return e
            else:
                return dsearch(e["children"], name)
        return {
            'name': name,
            'children': []
        }


    data = []
    lvl_products = [
        ('Cat 1', 'Sub Cat 1', 'lvl_3_cat-1'),
        ('Cat 1', 'Sub Cat 2', 'lvl_3_cat-2'),
        ('Cat 2', 'Sub Cat 3', 'lvl_3_cat-3')
    ]

    for lvl_product in lvl_products:
        print(lvl_product)
        parent = None; main_parent = None
        for _ in range(len(lvl_product)):
            element = dsearch(data, lvl_product[_])
            print(element)
            if parent:
                parent['children'].append(element)
            if main_parent is None:
                main_parent = parent
            parent = element
        data.append(main_parent)
    print(data)

My current output

[
    {
        "children": [
            {
                "children": [
                    {
                        "children": [],
                        "name": "lvl_3_cat-1"
                    },
                    {
                        "children": [],
                        "name": "lvl_3_cat-2"
                    }
                ],
                "name": "Sub Cat 1"
            },
            {
                "children": [
                    {
                        "children": [],
                        "name": "lvl_3_cat-1"
                    },
                    {
                        "children": [],
                        "name": "lvl_3_cat-2"
                    }
                ],
                "name": "Sub Cat 1"
            }
        ],
        "name": "Cat 1"
    },
    {
        "children": [
            {
                "children": [
                    {
                        "children": [],
                        "name": "lvl_3_cat-1"
                    },
                    {
                        "children": [],
                        "name": "lvl_3_cat-2"
                    }
                ],
                "name": "Sub Cat 1"
            },
            {
                "children": [
                    {
                        "children": [],
                        "name": "lvl_3_cat-1"
                    },
                    {
                        "children": [],
                        "name": "lvl_3_cat-2"
                    }
                ],
                "name": "Sub Cat 1"
            }
        ],
        "name": "Cat 1"
    }
]
recursion list dictionary algorithm python
2 Answers

You can use a tree-like data structure based on collections.defaultdict. This uses category levels as keys and sub-trees as values:

from collections import defaultdict


def tree():
    return defaultdict(tree)


def insert(node, value):
    if value:
        key, *remainder = value
        insert(node[key], remainder)


data = [
    ('Cat 1', 'Sub Cat 1', 'lvl_3_cat-1'),
    ('Cat 1', 'Sub Cat 2', 'lvl_3_cat-2'),
    ('Cat 2', 'Sub Cat 3', 'lvl_3_cat-3'),
]
root = tree()
for sample in data:
    insert(root, sample)

import json
print(json.dumps(root, indent=2, default=dict))

This results in the following data structure:

{
  "Cat 1": {
    "Sub Cat 1": {
      "lvl_3_cat-1": {}
    },
    "Sub Cat 2": {
      "lvl_3_cat-2": {}
    }
  },
  "Cat 2": {
    "Sub Cat 3": {
      "lvl_3_cat-3": {}
    }
  }
}

If you really want to keep the separate dict wrapper with "name" and "children" keys, you can convert the above tree with the following function:

def convert(node):
    return [{'name': key, 'children': convert(value)} for key, value in node.items()]

from pprint import pprint
pprint(convert(root))

Which gives as output:

[{'children': [{'children': [{'children': [], 'name': 'lvl_3_cat-1'}],
                'name': 'Sub Cat 1'},
               {'children': [{'children': [], 'name': 'lvl_3_cat-2'}],
                'name': 'Sub Cat 2'}],
  'name': 'Cat 1'},
 {'children': [{'children': [{'children': [], 'name': 'lvl_3_cat-3'}],
                'name': 'Sub Cat 3'}],
  'name': 'Cat 2'}]
user_37672390

How about this simple one-liner. This works recursively for any depth. -

from pprint import pprint

f = lambda x: {'name':x[0], 'children': f(x[1:])} if len(x)>0 else {}
output = [f(i) for i in _input]

pprint.pprint(output, sort_dicts=False)

[{'name': 'Cat 1',
  'children': {'name': 'Sub Cat 1',
               'children': {'name': 'lvl_3_cat-1', 'children': {}}}},
 {'name': 'Cat 1',
  'children': {'name': 'Sub Cat 2',
               'children': {'name': 'lvl_3_cat-2', 'children': {}}}},
 {'name': 'Cat 2',
  'children': {'name': 'Sub Cat 3',
               'children': {'name': 'lvl_3_cat-3', 'children': {}}}}]

If you can avoid the list(dict) inside each of the children and simply hold a dict, then it looks cleaner and the same as @a_guest output.

from pprint import pprint

f = lambda x: {x[0]:f(x[1:])} if len(x)>0 else {}
output = [f(i) for i in _input]

pprint(output, sort_dicts=False)

[{'Cat 1': {'Sub Cat 1': {'lvl_3_cat-1': {}}}},
 {'Cat 1': {'Sub Cat 2': {'lvl_3_cat-2': {}}}},
 {'Cat 2': {'Sub Cat 3': {'lvl_3_cat-3': {}}}}]
user_47559540
Related