How can I find the closest pair with the smallest difference in a single array?-CodePudding

I have a code that creates a list of 20 random integers between 1 and 1000. And In the case of multiple existences of closest pair, I have to display the smallest pair.

This is what I have so far:

import random

numbers = [random.randint(1, 100) for num in range(20)]
print(numbers)

CodePudding user response：

You can just do it by iterating over all possible pairs:

import random

numbers = [random.randint(1, 100) for num in range(20)]
print(numbers)

num1 = -1
num2 = -1

diff = 1001

for i in range(len(numbers)):
    for j in range(i 1,len(numbers)):
        if abs(numbers[i] - numbers[j]) == diff:
            if min(numbers[i],numbers[j]) < num1:
                num1 = min(numbers[i],numbers[j])
                num2 = max(numbers[i],numbers[j])
        if abs(numbers[i] - numbers[j]) < diff:
            diff = abs(numbers[i] - numbers[j])
            num1 = min(numbers[i],numbers[j])
            num2 = max(numbers[i],numbers[j])

print(diff,num1,num2)

CodePudding user response：

Since you only want the smallest pair, what you cant do is sort your list (or of copy of your list depending on your needs) with sort().

import random

numbers = [random.randint(1, 100) for num in range(20)]
numbers.sort()

print(numbers)

Then by iterating over the list, if a number is at more than 1 position, it is the smallest pair, so we can break the loop.

smallestPair = None
for n in numbers:
    indices = [i for i, x in enumerate(numbers) if x == n]
    if len(indices) > 1: # means there is more than 1 occurence of this number
        smallestPair = n
        break

print(smallestPair)

CodePudding user response：

I would suggesting using numpy:

import random
import numpy as np

numbers = np.array([random.randint(1, 100) for num in range(20)])
numbers.sort()
# calc diff:
diff = numbers[1:] - numbers[:-1]
# get index minimal diff:
argmin = diff.argmin()
pair = numbers[argmin:argmin 2]

Output:

print(numbers) # already sorted
>>> [ 1  6  7  8 11 15 18 37 47 54 60 61 61 73 73 78 82 85 87 94]
print(diff)
>>> [ 5  1  1  3  4  3 19 10  7  6  1  0 12  0  5  4  3  2  7]
print(pair) 
>>> array([61, 61])

This method will work in your case.

CodePudding user response：

If I understand the problem correctly, you get something like: Output:

[38, 88, 57, 19, 54, 13, 90, 99, 6, 87, 56, 42, 51, 77, 67, 77, 17, 31, 7, 87]

by your code and you want to find the two numbers that have the smallest difference?

I would start off by sorting the list: sorted_list = sorted(numbers)

Output:

[6, 7, 13, 17, 19, 31, 38, 42, 51, 54, 56, 57, 67, 77, 77, 87, 87, 88, 90, 99]

Then I would loop over the sorted list and keep track of the difference like in the code below:

min_difference = float('inf')  # initialize the minimum difference with   infinity
result = [None, None]
for i in range(1, len(sorted_numbers)):
    num_a = sorted_numbers[i-1]
    num_b = sorted_numbers[i]
    difference = num_b - num_a
    if difference < min_difference:
        min_difference = min(difference, min_difference)
        result = [num_a, num_b]
    if num_b - num_a == 0:  # Smallest difference is 0
        break

print(result)

Output:

[77, 77]

Hope this helps and hope I understood the problem correctly!