import sys
class Rank:
def __init__(self):
self.pair = [] # match pairs
self.rank = [] # sorted list
# def compare(self, a, b):
# print 'which ones do you like?'
# print ' [j]: %s, [k]: %s' % (a, b)
# key_input = raw_input(">>> ")
# if key_input == 'j':
# ans = (a, b)
# elif key_input == 'k':
# ans = (b, a)
# else:
# raise ValueError('please select by "j" or "k".')
# return ans
def compare(self, a, b):
ans = (max(a, b), min(b, a))
return ans
def first_matching(self, data):
n = len(data)
N = 1
if n == 0:
self.final()
elif n == 1:
self.rank.append(data[0])
self.tournament(self.narrowing(data[0]))
else:
while n >= N:
N = N*2
unseed = 2*n - N
first_winner = []
for i in range(unseed/2):
a, b = data.pop(0), data.pop(0)
ans = self.compare(a, b)
g, l = ans[0], ans[1]
first_winner.append(g)
self.pair.append((g, l))
data += first_winner
member = [(data[2*i], data[2*i+1]) for i in range(len(data)/2)]
return member
def tournament(self, data):
member = self.first_matching(data)
# print member
# if not member:
# print "member is empty"
# self.final()
if len(member) > 1:
while len(member) > 1:
winner = []
for p in member:
if (p[0], p[1]) in self.pair:
winner.append(p[0])
elif (p[1], p[0]) in self.pair:
winner.append(p[1])
else:
ans = self.compare(p[0], p[1])
g, l = ans[0], ans[1]
self.pair.append((g, l))
winner.append(g)
member = [(winner[2*i], winner[2*i+1]) for i in range(len(member)/2)]
if (member[0][0], member[0][1]) in self.pair:
top = member[0][0]
elif (member[0][1], member[0][0]) in self.pair:
top = member[0][1]
else:
ans = self.compare(member[0][0], member[0][1])
top, l = ans[0], ans[1]
self.pair.append((top, l))
self.rank.append(top)
# print self.rank
return top
def narrowing(self, x):
unsort_table = []
for_delete = []
for i, pair in enumerate(self.pair):
if x == pair[0]:
unsort_table.append(pair[1])
for_delete.append(i)
for j in for_delete:
self.pair[j] = None
self.pair = [k for k in self.pair if k is not None]
# print unsort_table
return unsort_table
def final(self):
for i, r in enumerate(self.rank):
print "%d: %s" % (i, r)
exit
import numpy as np
raw = [i for i in range(10)]
data = list(np.random.choice(raw, 10, replace=False))
rank = Rank()
def ranking(pair_lists):
result = rank.narrowing(rank.tournament(pair_lists))
return result
a = ranking(data)
qq = 1
while True:
a = ranking(a)
qq += 1
if qq > 40:
print "too many operation"
rank.final()
only one [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] n = 0 0: 9 1: 8 2: 7 3: 6 4: 5 5: 4 6: 3 7: 2 8: 1 9: 0 done
--------------------------------------------------------------------------- UnboundLocalError Traceback (most recent call last) <ipython-input-7-aab896df248f> in <module>() 11 qq = 1 12 while True: ---> 13 a = ranking(a) 14 qq += 1 15 if qq > 40: <ipython-input-7-aab896df248f> in ranking(pair_lists) 5 6 def ranking(pair_lists): ----> 7 result = rank.narrowing(rank.tournament(pair_lists)) 8 return result 9 <ipython-input-6-97729e784ae1> in tournament(self, data) 60 # print "member is empty" 61 # self.final() ---> 62 if len(member) > 1: 63 while len(member) > 1: 64 winner = [] UnboundLocalError: local variable 'member' referenced before assignment
data = [str(i) for i in range(10)]
rank = Rank()
def ranking(pair_lists):
result = rank.narrowing(rank.tournament(pair_lists))
return result
a = ranking(data)
qq = 1
while len(rank.rank) < len(data):
a = ranking(a)
qq += 1
if qq > 30:
break
which ones do you like? [j]: 0, [k]: 1 >>> k which ones do you like? [j]: 2, [k]: 3 >>> k which ones do you like? [j]: 4, [k]: 5 >>> k which ones do you like? [j]: 6, [k]: 7 >>> k which ones do you like? [j]: 8, [k]: 9 >>> k which ones do you like? [j]: 1, [k]: 3 >>> k which ones do you like? [j]: 5, [k]: 7 >>> k which ones do you like? [j]: 9, [k]: 3 >>> j which ones do you like? [j]: 7, [k]: 9 >>> k ['9'] which ones do you like? [j]: 8, [k]: 3 >>> j which ones do you like? [j]: 7, [k]: 8 >>> k ['9', '8'] which ones do you like? [j]: 3, [k]: 7 >>> k ['9', '8', '7'] which ones do you like? [j]: 6, [k]: 5 >>> j which ones do you like? [j]: 3, [k]: 6 >>> k ['9', '8', '7', '6'] which ones do you like? [j]: 5, [k]: 3 >>> j ['9', '8', '7', '6', '5'] which ones do you like? [j]: 4, [k]: 3 >>> j ['9', '8', '7', '6', '5', '4'] only one ['9', '8', '7', '6', '5', '4', '3'] which ones do you like? [j]: 2, [k]: 1 >>> j ['9', '8', '7', '6', '5', '4', '3', '2']
print rank.rank
print rank.pair
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0] []