CODEWITHSUNDEEP
pythonlistcyclecircular-list
Delgan
Delgan

Reputation: 19627

Minimum distance between two elements of a circular list?

Suppose I have a list like this:

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

Actually, I use my list like a cycle. This means that after G there is A, and before A, there is G.

I want to know what is the shortest distance between, for example, B and F.

Obviously, the answer is 3 as F -> G -> A -> B is shorter than B -> C -> D -> E -> F.

What is the more "pythonic" way to compute such distance?

What I though so far is quite ugly (assuming I know the index):

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)

Upvotes: 6

Views: 6593

Answers (2)

davidlc
davidlc

Reputation: 133

The accepted answer relies on modulo returning the answer with the same sign as the divisor. This is true in Python, but not all languages. (see: https://en.wikipedia.org/wiki/Modulo_operation#In_programming_languages)

The following code is less language specific:

def distance(len_my_list, idx_1, idx_2):
    dist = abs(idx_1 - idx_2)
    return min(len_my_list - dist, dist)

Upvotes: 10

Alex Riley
Alex Riley

Reputation: 176840

Since you're treating the list as circular, you can use modular arithmetic to find the two distances.

You just need to calculate the first index minus the second (modulo the list's length), and second index minus the first (modulo the list's length). The shortest path is the minimum of the two values.

In Python code, keeping your variable names:

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)

For your example, i is 3 and j is 4. Therefore the function returns 3.

Upvotes: 13

Related Questions