#!/usr/bin/python
# -*- coding: iso-8859-15 -*-

"""
Generator, um aus einer Liste l jedes Paar des Elements an der i-ten Stelle
und der nichtleeren Teilliste l[i+1:] zu erzeugen.
"""
def firstrests(list):
  first, rest = list[0], list[1:]
  while rest != []:
    yield first, rest
    first, rest = rest[0], rest[1:]

"""
Erzeugt eine Tabelle table, sodass table[j][m] angibt, wieviel Wähler den
m-ten Kandidaten über den n-ten bevorzugen.
"""
def make_pref_count_table(preferences):
  num = len(preferences[0])
  table = [ [0] * num for _ in xrange(num) ]
  for preference in preferences:
    for c, preferred in firstrests(preference):
      for d in preferred:
        table[c][d] += 1
  return table

"""
Das Maß für die Nähe einer gegebenen Präferenz zu den Präferenzen der 
Wähler (gemäß Kemeny-Young).
"""
def S(table, p):
  num = len(p)
  value = 0
  for j in xrange(0, num - 1):
    for m in xrange(j + 1, num):
      value += table[ p[j] ][ p[m] ]
  return value

"""
Generator, um aus einer Liste jedes Paar jeden Elements und den anderen 
Elementen der Liste zu erzeugen.
"""
def one_others(list):
  for i,_ in enumerate(list):
    if i == 0:
      yield list[i], list[1:]
    else:
      yield list[i], list[0:i] + list[i+1:]

"""
Generator, um alle Permutationen einer Liste zu erzeugen.
"""
def permutations(candidates):
  if len(candidates) == 1:
    yield candidates
  elif len(candidates) > 1:
    for one, others in one_others(candidates):
      for os in permutations(others):
        yield [one] + os

"""
Die soziale Wohlfahrtsfunktion gemäß Kemeny-Young
"""
def F(candidates, preferences):

  # erzeuge Tabelle für S_{\pi}(·,·)
  table = make_pref_count_table(preferences)

  # und suche aus allen Möglichkeiten die passendste ...
  best_pref = []
  best_value = None

  for preference in permutations(range(0, len(candidates))):
    curr_value = S(table, preference) 
    if best_value == None or curr_value > best_value:
      best_pref = preference
      best_value = curr_value

  # ... liefere Kandidatennamen statt nur Indizes
  return [candidates[i] for i in best_pref]

if __name__ == "__main__":
  candidates = ['a', 'b', 'c', 'd', 'e']
  a, b, c, d, e = 0, 1, 2, 3, 4
  preferences =\
      25 * [[b, a, d, e, c]] +\
      12 * [[e, d, c, b, a]] +\
      11 * [[c, e, a, b, d]] +\
      14 * [[d, a, b, e, c]] +\
      18 * [[e, b, d, c, a]] +\
      10 * [[c, d, a, e, b]] +\
      10 * [[c, d, e, b, a]]

  preference = F(candidates, preferences)
  print preference[0],
  for x in preference[1:]:
    print "<", x,
  print