Home > Software engineering >  Minimum distance between 2 values in a list, considering list is connected between end and start
Minimum distance between 2 values in a list, considering list is connected between end and start

Time:12-14

I want to find the minimum distance between any 2 values in a list. However, I need the minimum distance considering both 'clockwise' and 'anticlockwise' movement.

For example, I have the list [0, 4, 5, 6, 3, 1]. Say I want the distance between the pair (4,1)

Moving 'clockwise' the result is obviously 4 considering the difference in index. However, If one moves 'anti-clockwise' and considers the list connected, so 0 is a neighbour to 1. The distance would be 2, which is the result I want.

How can I achieve this?

I thought about joining the lists.

[0, 4, 5, 6, 3, 1, 0, 4, 5, 6, 3, 1]

However, then there are duplicates and I'm not sure how one would choose between these.

CodePudding user response:

There are a couple of ways to do this. One way is to note how you get reversed index to begin with. Pretend that index(1) == -1. The distance is now index(4) - index(1) = 1 1 = 2. -1 just means len(a) - 1 in this case. So for every pair of indices i1 and i2, you compute the two quantities max(i1, i2) - min(i1, i2), and min(i1, i2) len(a) - max(i1, i2), and take the smaller one.

If the values in the list are not unique, you will need to find all occurrences for each one, and use something like itertools.product to find the minimum distance.

  • Related