Sort elements to maximise amount of positive differences-CodePudding

I have a list of integers. Numbers can be repeated. I would like "sort" them in that way to get as many "jumps" (difference from the very next element to the current one is positive) as possible.

Examples:

[10, 10, 10, 20, 20, 20]  # only one "jump" from 10 to 20
[10, 20, 10, 20, 10, 20]  # three jumps (10->20, 10->20, 10->20) - the correct answer
[20, 10, 20, 10, 20, 10]  # two jumps

[11, 16, 8, 9, 4, 1, 2, 17, 4, 15, 9, 11, 11, 7, 19, 16, 19, 5, 19, 11]  # 9
[9, 11, 2, 19, 4, 11, 15, 5, 7, 11, 16, 19, 1, 4, 8, 11, 16, 19, 9, 17]  # 14
[2, 9, 11, 16, 17, 19, 4, 5, 8, 15, 16, 9, 11, 1, 7, 11, 19, 4, 11, 19]  # 15
[1, 2, 4, 5, 7, 8, 9, 11, 15, 16, 17, 19, 4, 9, 11, 16, 19, 11, 19, 11]  # 16

My totally inefficient (but working) code.:

def sol1(my_list):
    my_list.sort()
    final_list = []
    to_delete = []
    i = 0
    last_element = float('-inf')
    while my_list:
        if i >= len(my_list):
            i = 0
            for index in to_delete[::-1]:
                my_list.pop(index)
            if len(my_list):
                last_element = my_list.pop(0)
                final_list.append(last_element)
            to_delete = []
            continue

        curr_element = my_list[i]
        if curr_element > last_element:
            final_list.append(curr_element)
            last_element = curr_element
            to_delete.append(i)
        i  = 1
    return final_list

Does anyone know a way to optimize the solution? For now I'm iterating the list many times. It doesn't need to be in Python.

CodePudding user response：

The algorithm should deal with duplicate values such that first all first occurrences of the numbers appear in sorted order, then the second occurrences of the duplicates in sorted order, then the third occurrences, ...etc.

from collections import Counter 

lst = [11, 16, 8, 9, 4, 1, 2, 17, 4, 15, 9, 11, 11, 7, 19, 16, 19, 5, 19, 11]

result = [num for _,num in sorted(
    (i, num)
    for num, freq in Counter(lst).items()
        for i in range(freq)
)]

result will be:

[1, 2, 4, 5, 7, 8, 9, 11, 15, 16, 17, 19, 4, 9, 11, 16, 19, 11, 19, 11]

CodePudding user response：

I think this should be equivalent and only take O(n log n) time for sorting and O(n) time for the rest. Not tested/benchmarked thoroughly yet (don't have time right now and I'm only on a phone).

from collections import Counter, OrderedDict

arr = [11, 16, 8, 9, 4, 1, 2, 17, 4, 15, 9, 11, 11, 7, 19, 16, 19, 5, 19, 11]
d = OrderedDict(Counter(sorted(arr)))

ans = []
while d:
    ans  = d
    for x in list(d):
        d[x] -= 1
        if not d[x]:
            del d[x]
print(ans)

Another, inspired by trincot:

from collections import defaultdict
from itertools import count

arr = [11, 16, 8, 9, 4, 1, 2, 17, 4, 15, 9, 11, 11, 7, 19, 16, 19, 5, 19, 11]

d = defaultdict(count)
arr.sort(key=lambda x: (next(d[x]), x))

print(arr)

CodePudding user response：

give each element cumcount based on how many times it has appeared before. then sort first by cumcount and then by its value.

arr = [11, 16, 8, 9, 4, 1, 2, 17, 4, 15, 9, 11, 11, 7, 19, 16, 19, 5, 19, 11]
cumcount = []
d = dict.fromkeys(arr, 0)

for el in arr:
    cumcount.append(d[el])
    d[el]  = 1

[x[1] for x in sorted(zip(cumcount, arr))]
# [1, 2, 4, 5, 7, 8, 9, 11, 15, 16, 17, 19, 4, 9, 11, 16, 19, 11, 19, 11]