Упорядочить элементы в списке, чтобы аналогичные элементы находились дальше всего.

Question

Как я могу отсортировать плейлист так, чтобы песни одних и тех же художников были максимально распространены?

Хотя я не мог найти его или понять, я предполагаю, что есть быстрый и простой способ сделать это, что будет работать для всех видов установок, а также для двух аспектов: скажем (un) сортировка по художник и жанр, так что кроме того один жанр почти всегда сопровождается другим. (Так что это хороший микс)

Так что это один примерный список воспроизведения:

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 

И это будет один возможный оптимальный результат:

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)]