其實對於這個問題一個答案,我的問題是說是一個重複的,已爲我工作。所以maybie我的問題確實是重複的。雖然如果有人提出了更快的非隨機版本,我仍然會將該答案標記爲已接受。這是我修改的版本:
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)]
另一個問題不問如何實現多個方面的傳播,這樣是沒有重複的,據我可以告訴。 – Joschua