I've been using loops in order to solve my problem but my brain has stopped. I have a input as a list which contains couple of tuples like this:

input_list = [(1, 2), (2, 2), (3, 2), (5, 3), (7, 3), (4, 4)]

I would like to mix this tuples. Here are the steps:

1. Tuples have to be sorted in descending by its second element for every time. ((X, 2), (X, 3), (X, 4), (X, 2), (X, 3), (X, 2))
2. First element of the tuple must be the smallest value. ((1, 2), (5, 3), (4, 4), (2, 2), (7, 3), (3, 2))

Here is the output I would like to achieve:

output_list = [(1, 2), (5, 3), (4, 4), (2, 2), (7, 3), (3, 2)]

Can someone help me to find the algorithm to mix and convert to input list to the output list?

CodePudding user response：

You could use roundrobin from the itertools recipes. The function group_values sorts the data so that it can be used as an input for roundrobin.

from collections import defaultdict
from itertools import cycle, islice


def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    num_active = len(iterables)
    nexts = cycle(iter(it).__next__ for it in iterables)
    while num_active:
        try:
            for next_ in nexts:
                yield next_()
        except StopIteration:
            # Remove the iterator we just exhausted from the cycle.
            num_active -= 1
            nexts = cycle(islice(nexts, num_active))


def group_values(data):
    result = defaultdict(list)
    # sort by the second element first
    for entry in sorted(data, key=lambda x: (x[1], x[0])):
        result[entry[1]].append(entry)
    return result


def main():
    input_list = [(1, 2), (2, 2), (3, 2), (5, 3), (7, 3), (4, 4)]
    grouped_lists = group_values(input_list)
    result = list(roundrobin(*grouped_lists.values()))
    print(result)


if __name__ == '__main__':
    main()

group_values creates a dictionary that looks like this: {2: [(1, 2), (2, 2), (3, 2)], 3: [(5, 3), (7, 3)], 4: [(4, 4)]}. The function takes advantage of the fact that in modern versions of Python, entries in the dictionaries retain the order in which they were added.

The result is [(1, 2), (5, 3), (4, 4), (2, 2), (7, 3), (3, 2)], even if you shuffle the input list.

You might want to use a debugger or add some print functions in the code if you want to see what's happening.

CodePudding user response：

Sort the input by the second, then the first element. For each tuple in the sorted list, iterate a list of "slots" (lists) and add the tuple to the first slot whose last item is less than the tuple. If there's no such slot, create a new slot. Finally, join the slots into one list:

slots = []

for p in sorted(INPUT, key=lambda p: p[::-1]):
    for s in slots:
        if s[-1][1] < p[1]:
            s.append(p)
            break
    else:
        slots.append([p])


result = sum(slots, [])