Переупорядочить список таких, что каждый элемент сопровождается значением ближайшего к нему


Я просто начал играть с Python и надеялся получить некоторую обратную связь относительно качества следующий фрагмент. Это похоже на правильном языке Python? Что бы вы хотели изменить? Это небольшой скрипт, хорошо структурированным?

Краткое описание функциональных цель: упорядочить список таким образом, что каждый элемент с последующим значением ближайшего к нему, начиная с 20 (он же короткий-искать-первый алгоритм).

пример: [15, 24, 12, 13, 48, 56, 2]
становится: [24, 15, 13, 12, 2, 48, 56]

лучше пример: [22, 19, 23, 18, 17, 16]
становится: [19, 18, 17, 16, 22, 23]

fcfs_working = [15, 24, 12, 13, 48, 56, 2]
fcfs_track = []
track_number = 20
while len(fcfs_working) > 0:
    track_number = min(fcfs_working, key=lambda x:abs(x-track_number))
    fcfs_working.remove(track_number)
    fcfs_track.append(track_number)


378
10
задан 18 октября 2011 в 05:10 Источник Поделиться
Комментарии
3 ответа

while len(fcfs_working) > 0:

такой же, как и

while fcfs_working:

4
ответ дан 24 октября 2011 в 03:10 Источник Поделиться

С алгоритмической точки зрения, я хотел бы предложить другое решение (независимо от того, в Python как язык).

Здесь идет:

давайте предположим, что все элементы в данном массиве различны. в другом случае аналогичное решение, поэтому давайте сосредоточимся на сам алгоритм.


  1. Найти ближайшего числа, с точки зрения расстояния, из массива в заданном внешнем номер (20).

  2. отсортировать данный массив.

  3. найти значение в (1) в массиве. это можно сделать с помощью двоичного поиска.

  4. теперь, к главному: следующее значение будет либо слева от текущего значения или справа от текущего значения, так как расстояние между рядом значений тока одна, и массив не будет отсортирован (!).

  5. поэтому все, что вам нужно сделать, это провести два дополнительных индекса: внутренний левый и внутренний правый. эти индексы представляют собой внутренние границы "дыры", которая создается при создании нового списка.

Демонстрация:

исходный массив:


[22, 19, 23, 18, 17, 8]

отсортированный:


[8, 17, 18, 19, 22, 23]

первый элемент 19, с АБС(20-19) = 1 является ближней дистанции до 20.
давайте найдем 19 в отсортированный массив:


[8, 17, 18, 19, 22, 23]
^

теперь следующий элемент будет либо 18 или 22, так как массив уже отсортирован:


[8, 17, 18, 19, 22, 23]
? ^ ?

так что теперь у нас есть те внутренний левый и внутренний правый индексов, обозначим их как "ил" и "ИК".


[8, 17, 18, 19, 22, 23]
Ил ^ ИК

список результат: [19]

после 18 ближе к 19, чем 22, мы принимаем это, и смену Ил слева:


[8, 17, 18, 19, 22, 23]
Ил ^ ИК

список результат: [19, 18]

опять же, сейчас 17 ближе к 18, чем 22


[8, 17, 18, 19, 22, 23]
Ил ^ ИК

список результат: [19, 18, 17]

сейчас 22-это ближе к 17, чем 8, поэтому мы бы сдвинуть вправо-индекс:


[8, 17, 18, 19, 22, 23]
Ил ^ ИК

список результатов: [19, 18, 17, 22]

а остальное очевидно.

Опять же, это не имеет ничего общего с Python в частности. Это чисто алгоритм должен быть реализован на любом языке.

Этот алгоритм занимает время o(n журнал(N)) в то время, когда один из них предложил оригинальный плакат занимает o(п^2) времени.

3
ответ дан 23 ноября 2012 в 09:11 Источник Поделиться

Я не знаком с самым коротким-искать-первый алгоритм. Однако, он может работать для расчета дистанции каждое число в списке от текущей позиции, сортировки, а затем выводить результаты. Следовательно:

working = [15, 24, 12, 13, 48, 56, 2]
position = 20
distances = [(abs(position-x), x) for x in working]
>> [(5, 15), (4, 24), (8, 12), (7, 13), (28, 48), (36, 56), (18, 2)]
distances.sort()
>> [(4, 24), (5, 15), (7, 13), (8, 12), (18, 2), (28, 48), (36, 56)]
[x[1] for x in distances]
>> [24, 15, 13, 12, 2, 48, 56]

0
ответ дан 20 ноября 2012 в 09:11 Источник Поделиться