Das deutsche Python-Forum

Code: Alles auswählen

{'samstag': 5, 'sonntag': 7, 'montag': 8, 'donnerstag': 7}

Code: Alles auswählen

>>> import itertools
>>> for schedule in itertools.permutations('Bob Sue Jim Tony Alice Zane Tim'.split()):
...  print(schedule)
... 
('Bob', 'Sue', 'Jim', 'Tony', 'Alice', 'Zane', 'Tim')
('Bob', 'Sue', 'Jim', 'Tony', 'Alice', 'Tim', 'Zane')
('Bob', 'Sue', 'Jim', 'Tony', 'Zane', 'Alice', 'Tim')
('Bob', 'Sue', 'Jim', 'Tony', 'Zane', 'Tim', 'Alice')
('Bob', 'Sue', 'Jim', 'Tony', 'Tim', 'Alice', 'Zane')
('Bob', 'Sue', 'Jim', 'Tony', 'Tim', 'Zane', 'Alice')
('Bob', 'Sue', 'Jim', 'Alice', 'Tony', 'Zane', 'Tim')

Code: Alles auswählen

import pprint
from random import randint, sample
from itertools import permutations, islice, imap, cycle
from operator import itemgetter


first = itemgetter(0)


def compose(f, g):
    return lambda x: g(f(x))


def take(n, iterable):
    "Return first n items of the iterable as a list"
    return list(islice(iterable, n))


def generate_team_sizes(m, n):
    it = iter([1] * n)
    for i in xrange(n - 1):
        yield sum(take(randint(0, m), it))
    yield sum(it)


max_team_size = 3

workers = 'Bob Sue Jim Tony Alice Zane Tim'.split()

days = 'mon tue wed thu fri sat sun'.split()

by_day = compose(first, {day: i for i, day in enumerate(days)}.__getitem__)

team_size_per_day = zip(sample(days, len(days)),
                        generate_team_sizes(max_team_size, len(days)))
team_size_per_day.sort(key=by_day)

preferences = {}
for worker in workers:
    day_a, day_b = sample(days, 2)
    preferences[day_a, worker] = 2
    preferences[day_b, worker] = 1


tmp1 = ([(day, take(size, each)) for day, size in team_size_per_day]
        for each in imap(cycle, permutations(workers)))

tmp2 = ([[day, frozenset((w, preferences.get((day, w), 0)) for w in team)]
            for day, team in each]
        for each in tmp1)

tmp3 = (tuple((day, wps, sum(pref for w, pref in wps)) for day, wps in each)
        for each in tmp2)


def by_weight_desc(rows):
    prefs = [pref for day, wps, prefsum in rows for w, pref in wps]
    return prefs.count(0) * 2 - sum(prefs)


result = sorted(set(tmp3), key=by_weight_desc)
pprint.pprint(team_size_per_day)
print
pprint.pprint(sorted(preferences.iteritems(), key=compose(first, by_day)))
print
for solution in result:
    if all(pref for day, wps, prefsum in solution for w, pref in wps):
        print 'A solution for all preferred days was found:'
        print
        pprint.pprint(solution)
        break
else:
    if result:
        solution = result[0]
        print 'A solution for all preferred days could not be found.'
        print 'Best match is:'
        print
        pprint.pprint(solution)
    else:
        print 'No solution could be found.'

Code: Alles auswählen

from __future__ import division
from random import randint, sample
from itertools import permutations, product, starmap
from operator import itemgetter
from collections import defaultdict
import pprint


first = itemgetter(0)


def compose(f, g):
    return lambda x: g(f(x))


def randints_upto_total(min_int, max_int, total):
    for _ in xrange(total - 1):
        n = randint(min_int, min(max_int, total))
        yield n
        total -= n
    yield total


def variance(numbers):
    numbers = iter(numbers)
    m = next(numbers)
    s = 0
    i = 2
    for i, x in enumerate(numbers, start=2):
        # See Knuth TAOCP vol 2, 3rd edition, page 232
        n = m
        m += (x - m) / i
        s += (x - m) * (x - n)
    return s / (i - 1)


workers = 'Bob Sue Jim Tony Alice Zane Tim'.split()
days = 'mon tue wed thu fri sat sun'.split()

by_day = compose(first, {day: i for i, day in enumerate(days)}.__getitem__)

team_size_per_shift = zip(sample(days, len(days)),
                          randints_upto_total(0, 3, len(days)))
team_size_per_shift.sort(key=by_day)

preferences = {}
for worker in workers:
    day_a, day_b = sample(days, 2)
    preferences[day_a, worker] = 2
    preferences[day_b, worker] = 1


def by_weight(shifts):
    rank = 0
    zeros = 0
    attendance = defaultdict(int)
    for day, team in shifts:
        for worker, preference in team:
            attendance[worker] += 1
            if preference:
                rank += preference
            else:
                zeros += 1
    return -variance(attendance.itervalues()), -zeros, rank


def shift(day, team_size):
    for team in permutations(workers, team_size):
        yield day, frozenset((worker, preferences.get((day, worker), 0))
                             for worker in team)


pprint.pprint(team_size_per_shift)
print
pprint.pprint(sorted(preferences.iteritems(), key=compose(first, by_day)))
print
result = max(set(product(*starmap(shift, team_size_per_shift))), key=by_weight)
if result:
    if all(preference for day, team in result
                        for worker, preference in team):
        print 'A solution for all preferred days was found:'
    else:
        print 'A solution for all preferred days could not be found.'
        print 'Best match is:'
    print
    pprint.pprint(result)
else:
    print 'No solution could be found.'