如何确定排名算法标准

Question

我想确定是否有更好的算法可用于下面的问题集，而不是我已经提出的蛮力方法。鉴于最初的循环是n ** n，这很快就会下降。

该算法的要点是，我有一组排名和与排名项目相关的数据。从这我需要确定什么标准被用来提出排名顺序。例如，如果排名是Ben，Sam，然后是Hal，那么使用的标准将是GPA。

criteria = ['Height', 'Weight', 'GPA'] 

candidates = {'Ben': (72,205,4.0),'Sam': (65,220,3.8),'Hal': (74,210,3.6)} 

def base10toN(num, base): 
    converted_string, modstring = "", "" 
    currentnum = num 
    while currentnum: 
     mod = currentnum % base 
     currentnum = currentnum // base 
     converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string 
    return converted_string 

def get_relevant_criteria(criteria, candidates, ranking): 
    l = len(criteria) 

    max_score = 0 
    max_criteria =() 

    for x in xrange(1,l**l): 
     pattern = str(base10toN(x,l)).rjust(3,'0') 

     prev_score = 0 
     isvalid = True 

     for candidate in ranking[::-1]: 
      new_score = score_criteria(pattern, candidates[candidate]) 
      if new_score < prev_score: 
       isvalid = False 
       break 
      prev_score = new_score 
     if isvalid: 
      return [criteria[x] + " (x"+pattern[x]+")" for x in xrange(0,len(pattern)) if pattern[x] != '0'] 
    return None 

def score_criteria(pattern, values): 
    score = 0 
    for x in xrange(0,len(pattern)): 
     score += int(pattern[x]) * values[x] 
    return score 

print get_relevant_criteria(criteria, candidates, ('Ben', 'Sam', 'Hal')) # GPA 
print get_relevant_criteria(criteria, candidates, ('Sam', 'Hal', 'Ben')) # Weight 
print get_relevant_criteria(criteria, candidates, ('Hal', 'Ben', 'Sam')) # Height 

Answer 1

您有排名，因此应该很容易以线性方式执行此操作，请使用以人名作为键和数据作为值的字典。通过给出的排序顺序以及数据中的每个项目，记住最后一个人的值是什么，并检查该参数的当前值是否更大（如果是反向排序则更小）。一旦你击中了一个不存在的地方，你可以消除该属性。当多个属性可以被使用时，这也会给你正确的答案。

criteria = ['Height', 'Weight', 'GPA'] 
def get_relevant_criteria(criteria, candidates, ranking): 
    answer = "" 
    possible = [1] * len(criteria) 
    previous = [0] * len(criteria) 
    direction = [0] * len(criteria) 
    for name in ranking: 
     for (index, parameter) in enumerate(candidates[name]): 
      if parameter < previous[index]: 
        if direction[index] == 0: 
         direction[index] = -1 
        if direction[index] == 1: 
         possible[index] = 0 
      if parameter > previous[index]: 
        if direction[index] == 0: 
         direction[index] = 1 
        if direction[index] == -1: 
         possible[index] = 0 
     previous = candidates[name] 
    for i in range(len(criteria)): 
     if possible[i] == 1: 
      answer += criteria[i]+" " 
    return answer 

candidates = {'Ben': (72,205,4.0),'Sam': (65,220,3.8),'Hal': (74,210,3.6)} 
print order_criteria(criteria, candidates, ('Ben', 'Sam', 'Hal')) # GPA 
print order_criteria(criteria, candidates, ('Sam', 'Hal', 'Ben')) # Weight 
print order_criteria(criteria, candidates, ('Hal', 'Ben', 'Sam')) # Height 

candidates2 = {'Ben': (72,100,1.0), 'Sam': (72,90,2.0), 'Hal': (64,200,4.0)} 
print order_criteria(criteria, candidates2, ('Ben', 'Sam', 'Hal')) # Height GPA 
print order_criteria(criteria, candidates2, ('Sam', 'Hal', 'Ben')) # 
print order_criteria(criteria, candidates2, ('Hal', 'Ben', 'Sam')) # Weight 

注意的是，虽然你可能不得不在最坏的​​情况下至少一次触摸数据的每一个元素，它在人们的数量成线性比例，并与参数的数量成线性比例（这是基本的数人数乘以参数的数量）...没有数据被触摸超过一次。

我修改了它，以便它不必提前知道排序的顺序（ASC或DESC）。请注意，当多个参数可能是排序属性并且它们中的任何一个都不起作用时，它是如何处理的。