Finding next max value from index of nested lists in python?-CodePudding

I'm trying to find the next maximum value of nested lists, I already have a nested list sorted by bubblesort, I need to take the largest element of each nested list and insert it into the solution vector, until the solution vector is sorted. P.S: I can't delete the element from the initial nested list, only find the next maximum value. See the image at the bottom as an example:

Nested_list = [[1, 7, 9], [4, 5, 6], [2, 3, 8], [0]]

The way I devised deleted the largest vector from the original list, which was quite time consuming, I believe that just moving the index to the next largest value will consume less time:

def bubbleSort(array):
    n = len(array)-1
    for i in range(n):
        for j in range(0, n-i):
            if array[j] > array[j 1]:
                array[j], array[j 1] = array[j 1], array[j]
            else:
                continue
    return array

def ordena_lista(output): 
    for sublista in output:
        bubbleSort(sublista)
       
        
def maior_valor_lista(output):
    return list(el[-1] for el in output)


def nested_remove(L, x):
    if x in L:
        L.remove(x)
    else:
        for element in L:
            if type(element) is list:
                nested_remove(element, x)

b = list(random.sample(range(10), 10))
n= m.floor(m.sqrt(len(b)))
output=list([b[i:i   n] for i in range(0, len(b), n)])
ordena_lista(b)
while output:
        valores_maximo = maior_valor_lista(output)
        var = max(valores_maximo, key=int)
        final = [var]   final
        nested_remove(output, var)
        output = list(filter(None, output))

CodePudding user response：

The simplest solution would be the following,

from functools import reduce
from operator import add


def sort_nested_list(nested_list):
   return sorted(reduce(add, nested_list))

but, without knowing the exact implementation details of python's sorted, I can't tell you if it takes advantage of your pre-sorting.

If we know the sublists are sorted, and we are allowed to copy the list, and we know how many elements there are in total, we can write the following,

import math
from copy import deepcopy


def get_max_and_pop(nested_list):
    """ find the maximum element of a sublist of nested_list, remove it from the sublist, and return it """
    print(f"get_max_and_pop says: {nested_list}")
    return max(nested_list, key=lambda x: x[-1:]).pop()


def sort_nested_list_whose_sublists_are_sorted(nested_list, n_elements):
    nested_list_copy = deepcopy(nested_list)
    return [get_max_and_pop(nested_list=nested_list_copy) for _ in range(n_elements)][::-1]

edit: without knowledge of the number of elements, we can write,

from copy import deepcopy


def sort_nested_list_whose_sublists_are_sorted_iter(nested_list):
    nested_list_copy = deepcopy(nested_list)
    while any(nested_list_copy):
        yield max(nested_list_copy, key=lambda x: x[-1:]).pop()

CodePudding user response：

This amounts to a bizarre, woefully inefficient and completely unnecessary sorting algorithm but here goes anyway:

Nested_list = [[9, 7, 1], [4, 5, 6], [2, 3, 8], [0]]

for e in Nested_list:
    e.sort()

Output_list = []

Nested_list_copy = [[e_ for e_ in e] for e in Nested_list]

element_count = sum(len(e) for e in Nested_list)

for _ in range(element_count):
    m = None
    for i, e in enumerate(Nested_list_copy):
        if e:
            tm = e[-1]
            if m is None or tm > m:
                m = tm
                k = i
    Output_list.insert(0, Nested_list_copy[k].pop())

print(Nested_list)
print(Output_list)

Output:

[[1, 7, 9], [4, 5, 6], [2, 3, 8], [0]]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]