Minimum distance between two elements of a circular list?

Question

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)

I guess your question belongs to Code Review instead of StackOverflow... you can get better response there... — Ankit
– Ankit, Commented Jun 27, 2015 at 21:15
@Ankit It reeks like example code though, which might be a problem. — Mast
– Mast, Commented Jun 27, 2015 at 21:19

Alex Riley · Accepted Answer · 2015-06-27 21:20:32Z

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.

davidlc · Accepted Answer · 2019-12-04 01:45:05Z

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)

Collectives™ on Stack Overflow

Minimum distance between two elements of a circular list?

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related