sorting python list in recursive manner

Question

As input I will be getting lists of lists which can up to n-levels and it will vary every time. Suppose, I have a list

[[2, 1, 3], 4, [2, 3], 7, 1, [9, [4, 2], 5]]

here I want to sort this list and expected output is

[1, 4, [2, 3], [1, 2, 3], 7, [5, [2, 4], 9]]

Here, first sorting is happening based of elements and then based on sum of elements inside list.

code:

input_freq = [[2,1,3],4,[2,3],7,1,[9,[4,2],5]]

res = []

def sortFreq(input_freq):
    elements = []
    list_of_elements = []

    for each in input_freq:
        if isinstance(each, list):
            print "list"
            list_of_elements.append(each)
            each.sort()
        else:
            elements.append(each)
            elements.sort()

    print elements
    print list_of_elements

sortFreq(input_freq)

expected output:

[1, 4, [2, 3], [1, 2, 3], 7, [5, [4, 2], 9]]

but my code returns the wrong result:

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

What is the sum for [9, [4, 2], 5]? The sum of the flattened elements, so 9 + 4 + 2 + 5 == 20? — Martijn Pieters
– Martijn Pieters, Commented Dec 8, 2017 at 8:09
Well first I don't see you using the sum of the elements of your nested lists at any point, so you're probably at least missing that. — Marc Z
– Marc Z, Commented Dec 8, 2017 at 8:13
Secondly, you said "recursive manner" but you implemented an iterative algorithm, are you sure it is what you're aiming for? — Marc Z
– Marc Z, Commented Dec 8, 2017 at 8:14
Your input is not a list of lists as you claim. It is a list of <type 'list'> <type 'int'> <type 'list'> <type 'int'> <type 'int'> <type 'list'> — Marichyasana
– Marichyasana, Commented Dec 8, 2017 at 8:22

Martijn Pieters · Accepted Answer · 2017-12-08 08:14:34Z

You'll have to work your way down to the nested levels first, then sort the parent levels as the recursive call returns. I'm going to assume you want to return a new list (and not sort in place):

def nested_sort(l):
    def sort_key(e):
        if isinstance(e, list):
            return sum(sort_key(inner) for inner in e)
        return e
    return sorted(
        [nested_sort(e) if isinstance(e, list) else e for e in l],
        key=sort_key)

The sort key has to recursively sum nested lists, so this can be kind of expensive if you have many nested levels. In that it may be worth adding a cache based on the identity of the list being summed:

def nested_sort(l, _sum_cache=None):
    if _sum_cache is None:
        _sum_cache = {}
    def sort_key(e):
        if isinstance(e, list):
            e_id = id(e)
            if e_id not in _sum_cache:
                _sum_cache[e_id] = sum(sort_key(inner) for inner in e)
            return _sum_cache[e_id]
        return e
    return sorted(
        [nested_sort(e, _sum_cache) if isinstance(e, list) else e for e in l],
        key=sort_key)

Demo:

>>> nested_sort([[2, 1, 3], 4, [2, 3], 7, 1, [9, [4, 2], 5]])
[1, 4, [2, 3], [1, 2, 3], 7, [5, [2, 4], 9]]

Paul Panzer · Accepted Answer · 2017-12-08 08:46:31Z

0

Here is a solution that has the benefit of doing every sum only once. It is also quite short:

import operator

def sort_lol(lol):
    srtd, sums = zip(*sorted((sort_lol(el) if isinstance(el, list) else (el, el) 
                              for el in lol), key=operator.itemgetter(1)))
    return list(srtd), sum(sums)

lst = [[2,1,3],4,[2,3],7,1,[9,[4,2],5]]
print(sort_lol(lst))

# ([1, 4, [2, 3], [1, 2, 3], 7, [5, [2, 4], 9]], 43)
# note that the function returns the sorted list and the total (43 here)

edited Dec 8, 2017 at 8:46

answered Dec 8, 2017 at 8:39

Paul Panzer

53.3k3 gold badges59 silver badges103 bronze badges

2 Comments

Mahesh Karia Over a year ago

But I does not return list, it is returning tuples. I dont want to change data structure here.

Paul Panzer Over a year ago

@MaheshKaria Oops, fixed.

Collectives™ on Stack Overflow

sorting python list in recursive manner

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related