Заказать список по всем элементам в Python

Question

Я хочу отсортировать список по каждому элементу.

Пример:

myCmpItem = '511' 
myList = ['111','222','333','444','555','123'] 

(some magic) 

mySortedList = ['111', '222', '333', '123', '444', '555'] 

Как алгоритм должен работать:

• Сравнить каждую цифру текущего элемента в MyList с myCmpItem
  • Для первого элемента в списке было бы например:
  • Разница между 5 и 1 равна 4
  • разница между 1 и 1 0
  • Разница между 1 и 1 0
  • Разница между этими двумя числами 4 (сумма сравнения цифр)
• Сделайте то же самое для всех остальных элементов
• Заказать список по этому расчетному сходству

Я мог бы код это с много для-петли, но я на самом деле ищу более быстрый способ сделать это. Есть ли какой-нибудь алгоритм, который делает что-то подобное? Быстро?

Дальнейшие ограничения

• В моем примере все элементы имеют длину 3, в реальном сценарии они имеют длину 25
• Все детали имеют одинаковую длину, длина (MyList [х]) == 25 всегда верно
• Элементы могут быть строки, Интс, поплавки или что-то лучше подходит к алгоритму
• есть только цифры от 1 до 5

Фон

Все цифры элемента - это ответы на вопросы, и я хочу найти наиболее похожие ответы на заданные ответы. Таким образом, «123» означает, что пользователь ответил на вопросы 1 = ответ 1, вопрос 2 = ответ 2, вопрос 3 = ответ 3. Это вопросы с множественным выбором с 25 вопросами в целом (= длина 25), и всегда есть 5 разных возможно ответить (это цифры 1-5).

PS: Это первый вопрос, который я задал в Stackoverflow, поэтому, пожалуйста, будьте любезны со мной. Я уже много часов работал в Интернете, но я не мог найти решения, поэтому я спросил здесь. Надеюсь, все в порядке. Также английский не является моим родным языком.

Ответ (спасибо всем участникам!) Ответ

@larsmans' (https://stackoverflow.com/a/10790714/511484) объясняет очень хорошо, как решить эту проблему с разумной скоростью. Вы можете даже ускорить алгоритм, вычисляя расстояния между каждой цифрой заранее, см. Сообщение @ gnibbler (https://stackoverflow.com/a/10791838/511484). Все остальные ответы были также хороши и правильны, но я обнаружил, что у @larsmans было лучшее объяснение. Спасибо всем за помощь!

Answer 1

Во-первых, составить список целых чисел от myCmpItem сделать вычитание возможно.

myCmpItem = map(int, myCmpItem) 

Затем определим функцию, которая вычисляет расстояние между элементом и myCmpItem. Нам также нужно отобразить элементы в списки целых чисел. Остальное - это просто формула ванили для L1 distance (математическое название «разницы», которую вы вычисляете).

def dist(item): 
    item = map(int, item) 
    return sum(abs(item[i] - myCmpItem[i]) for i in xrange(len(item))) 

Затем, используйте эту функцию как функцию key для сортировки.

sorted(myList, key=dist) 

(PS: Вы уверены, что L1 расстояние имеет смысл для этого приложения с помощью выражает предположение, что ответить на 1 больше похоже на ответ 2, чем ответить на 3 и т.д. Если это не так, Hamming distance может быть более уместным.)

Answer 2

def cmpWith(num): 
    def compare(item): 
     """ calculate the difference between num and item """ 
     return sum(
      abs(int(n) - int(x)) # cast to int to make the substraction possible 
      for x,n in zip(item, num) # zip makes pairs from both lists 
     ) 

    return compare 

lst = ['111','222','333','444','555','123'] 
print sorted(lst, key=cmpWith('511')) 

Answer 3

Как насчет этого?

myCmpItem = '511' 
myList = ['111','222','333','444','555','123'] 

def make_key(x): 
    diff = 0 
    for a, b in zip(x, myCmpItem): 
     diff += abs(int(a)-int(b)) 
    return diff 

mySortedList = sorted(myList, key=make_key) 

print mySortedList 

Answer 4

С lambda и списком пониманием:

sorted(myList, key=lambda item: sum([abs(int(x) - int(y)) for x, y in zip(item, myCmpItem)]) 

Answer 5

Предвычислением таблицы расстояний может быть быстрее, чем преобразование каждой цифры int

myCmpItem = '511' 
myList = ['111','222','333','444','555','123'] 

# only need to compute this dict once 
dists = {(i,j):abs(int(i)-int(j)) for i in '12345' for j in '12345'} 

print sorted(myList, key=lambda j: sum(dists[i] for i in zip(j, myCmpItem))) 

На моем компьютере, это в 2,9 раза быстрее чем larsmans отвечает за строки 100000 x 25 символов