Минимальное расстояние между двумя элементами кругового списка?

Предположим, у меня есть такой список:

my_list = [A, B, C, D, E, F, G]

На самом деле, я использую свой список как цикл. Это означает, что после G есть Aи до A, есть G,

Я хочу знать, что самое короткое расстояние между, например, B а также F,

Очевидно, ответ 3 как F -> G -> A -> B короче чем B -> C -> D -> E -> F,

Какой более "питонный" способ вычислить такое расстояние?

То, что я до сих пор, довольно некрасиво (при условии, что я знаю индекс):

def distance(len_my_list, idx_1, idx_2):
    right = max(idx_1, idx_2)
    left = min(idx_1, idx_2)
    dist_1 = right - left
    dist_2 = (len_my_list - right) + left
    return min(dist_1, dist_2)
Источник

1 ответ

Решение

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

Вам просто нужно вычислить первый индекс минус второй (по модулю длины списка), а второй индекс минус первый (по модулю длины списка). Кратчайший путь - это минимум двух значений.

В коде Python, сохраняя имена ваших переменных:

def distance(len_my_list, idx_1, idx_2):
    i = (idx_1 - idx_2) % len_my_list
    j = (idx_2 - idx_1) % len_my_list
    return min(i, j)

Для вашего примера i 3 и j равно 4. Поэтому функция возвращает 3.

Источник

Принятый ответ полагается на то, что по модулю возвращается ответ с тем же знаком, что и делитель. Это верно для Python, но не для всех языков. (см.: https://en.wikipedia.org/wiki/Modulo_operation)

Следующий код менее специфичен для языка:

def distance(len_my_list, idx_1, idx_2):
    dist = abs(idx_1 - idx_2)
    return min(len_my_list - dist, dist)
Источник
Другие вопросы по тегам