Sort items in a list so that similar items are farthest from each other

Question

How can I sort the playlist so that the songs of the same artists are as widespread as possible?

Although I could not find anyone or understand, I assume that there is a quick and easy way to do this, which will work for all kinds of installations, as well as for two aspects: let's say (un) sort by artist and genre, so in addition to one genre almost always follows another. (so it's a nice mix)

So this is one sample playlist:

from collections import namedtuple

Song = namedtuple('Song', ('artist', 'title', 'length'))

# the length is not correct
Mozart_1 = Song('Mozart', 'Don Giovanni', 3.5)
Mozart_2 = Song('Mozart', 'Serenata Notturna', 2.98)
Mozart_3 = Song('Mozart', 'Violin Concerto No. 3 in G, 1st Movement', 8.43)
Bach_1 = Song('Bach', 'Air', 6.18)
Bach_2 = Song('Bach', 'Toccata in D Minor', 12.44)
Beethoven_1 = Song('Beethoven', 'Für Elise', 2.47)

playlist = [Beethoven_1, Mozart_3, Bach_1, Mozart_2, Mozart_1, Bach_2] # unsorted

And this will be one of the possible optimal results:

OPTIMUM = [Mozart_1, Bach_1, Mozart_2, Beethoven_1, Mozart_3, Bach_2]

Answer 1

, , . , , . , - , - . :

import random
from collections import namedtuple, defaultdict
from operator import attrgetter

Song = namedtuple('Song', ('artist', 'title', 'length'))

# the length is not correct
Mozart_1 = Song('Mozart', 'Don Giovanni', 3.5)
Mozart_2 = Song('Mozart', 'Serenata Notturna', 2.98)
Mozart_3 = Song('Mozart', 'Violin Concerto No. 3 in G, 1st Movement', 8.43)
Bach_1 = Song('Bach', 'Air', 6.18)
Bach_2 = Song('Bach', 'Toccata in D Minor', 12.44)
Beethoven_1 = Song('Beethoven', 'Für Elise', 2.47)

playlist = [Beethoven_1, Mozart_3, Bach_1, Mozart_2, Mozart_1, Bach_2] # unsorted

# one possible optimum
# OPTIMUM = [Mozart_1, Bach_1, Mozart_2, Beethoven_1, Mozart_3, Bach_2]


def optimize(items, quality_function, stop=1000, randrange=random.randrange):
    length = len(items)
    no_improvement = 0
    best = 0
    while no_improvement < stop:
        i = randrange(length)
        j = randrange(length)
        copy = items[:]
        copy[i], copy[j] = copy[j], copy[i]

        q = quality_function(copy)
        if q > best:
            items, best = copy, q
            no_improvement = 0
        else:
            no_improvement += 1
    return items


def quality_maxmindist(items):
    s = 0
    for item in set(items):
        indcs = [i for i in range(len(items)) if items[i] == item]
        if len(indcs) > 1:
            s += sum(1. / (indcs[i+1] - indcs[i]) for i in range(len(indcs)-1))
    return 1. / s


def spread_equal_items_apart(items, key, stop=optimize.__defaults__[0]):
    keys, key_to_items = keys_and_key_to_items_dict(items, key)
    keys = optimize(keys, quality_maxmindist)
    re = []
    for k in keys:
        re.append(key_to_items[k].pop())
    return re


def keys_and_key_to_items_dict(items, key):
    key_to_items = defaultdict(list)
    keys = []
    for i in items:
        k = key(i)
        keys.append(k)
        key_to_items[k].append(i)
    return keys, key_to_items


if __name__ == '__main__':
    new = spread_equal_items_apart(playlist, attrgetter('artist'))
    print(new)

, new :

[Song(artist='Mozart', title='Don Giovanni', length=3.5),
 Song(artist='Bach', title='Toccata in D Minor', length=12.44),
 Song(artist='Beethoven', title='Für Elise', length=2.47),
 Song(artist='Mozart', title='Serenata Notturna', length=2.98),
 Song(artist='Bach', title='Air', length=6.18),
 Song(artist='Mozart', title='Violin Concerto No. 3 in G, 1st Movement', length=8.43)]

Answer 2

, ( ):

from collections import defaultdict
from itertools import count

by_artist = defaultdict(count)
new_list = sorted(playlist, key=lambda L: next(by_artist[L.artist]))

:

[Song(artist='Beethoven', title='Fur Elise', length=2.47),
 Song(artist='Mozart', title='Violin Concerto No. 3 in G, 1st Movement', length=8.43),
 Song(artist='Bach', title='Air', length=6.18),
 Song(artist='Mozart', title='Serenata Notturna', length=2.98),
 Song(artist='Mozart', title='Don Giovanni', length=3.5),
 Song(artist='Bach', title='Toccata in D Minor', length=12.44)]

:

[Song(artist='Beethoven', title='Fur Elise', length=2.47),
 Song(artist='Mozart', title='Violin Concerto No. 3 in G, 1st Movement', length=8.43),
 Song(artist='Bach', title='Air', length=6.18),
 Song(artist='Mozart', title='Serenata Notturna', length=2.98),
 Song(artist='Bach', title='Toccata in D Minor', length=12.44),
 Song(artist='Mozart', title='Don Giovanni', length=3.5)]