순위 알고리즘 기준을 결정하는 방법

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)를 미리 알 필요가 없도록 수정했습니다. 여러 매개 변수가 정렬 속성이었을 때와 처리하지 않을 때 처리하는 방법에 유의하십시오.