چگونه می توانم دو نزدیک‌ترین اعداد به هم رو توی یه آرایه پیدا کنم؟

دوستان سوال من یه خرده ریاضی داره یعنی با برنامه نویسی می خوام یه کاری کنم شبیه ریاضی. لازم دارم تمام آیتم های یه آرایه رو بررسی کنم (که میدونم اینجا یه لوپ باید بزنم) و در نهایت دو عددی که از همه به هم نزدیک‌ترن رو پیدا کنم. با زبان پی اچ پی php هم اینو میخوام پیاده‌سازی کنم. مثلا این آرایه رو در نظر بگیرید:

$array = [20, 1, 5, 10, 7, 16];

با توجه به توضیحی که دادم الان توی مثال بالا باید بتونم اعداد 5 و 7 رو پیدا کنم. چون:

7 - 5 = 2

و این 2 کوچکترین عدد بین تفاضل سایر اعداد توی آرایه است. پس دقیقا 5 و 7 نزدیک‌ترین دو عدد توی آرایه هستند. کسی می‌‍دونه چطور می تونم این کار رو انجام بدم؟ خودم این کد رو زدم و میدونم که ناقصه:

$keep = $array[0];
$diff = $array[1] - $array[0];
foreach ($arrayas $item) {
    if ( ($keep - $item) < $diff && $keep != $item ) {
        $diff = $item;
    }
}

لطفا کمکم می کنید این کد رو تمومش کنم ؟ مرسی

برای اینکه بتونید 2 عددی که نسبت به سایر اعداد توی آرایه بهم نزدیک تر هستن رو پیدا کنید، اولی چیزی که به ذهن میرسه اینه که تمام اعداد توی آرایه رو یه بار با هم دیگه - دو به دو - مقایسه کنید. به عبارت بهتر، 2 حلقه تو در تو.

مثال کوتاه:

با فرض اینکه آرایه ما حاوی اعداد 1، 2 و 3 باشه، ما نیاز داریم مراحل زیر رو طی کنیم:

• در مرحله اول 1 رو با 2 و 3 مقایسه کنیم
• سپس 2 رو با 1 و 3
• و در مرحله آخر هم 3 رو با 1 و 2.

حالا به عنوان یک حرکت برای بهینه تر کردن این الگوریتم، چقدر خوبه که کاری کنیم که اعدادی که یک بار باهم مقایسه شدن دیگه باهم مقایسه نشن. یعنی اگه 1 و 2 یکبار باهم مقایسه شدن، دیگه 2 و 1 مقایسه نشن. یکی از بهترین الگوریتم ها برای پیاده سازی این فرایند، الگوریتم Binomial coefficient هستش:

(n)            n!
(k)   →   ─────────────
           k! * (n - k)!

در فرمول بالا n تعداد تمام آیتم های آرایه هست و k تعداد آیتم هایی که شما انتخاب می کنید برای مقایسه شدن.

که در مثال شما فرمول به این شکل باید نوشته بشه:

n = 6 //Array elements
k = 2 //Two values which you compare

     6!                  720
─────────────   →   ─────────────   = 15 comparison
2! * (6 - 2)!            2  *  24

تصویر سازی الگوریتم فوق:

جهت پیاده سازی توی کد هم، همونطور که گفتم باید شما روی تمام آیتم های آرایه 2 تا لوپ (حلقه) تو در تو بزنی، فقط خیلی بهینه تر میشه که اگه طوری کدش رو بنویسی که از مقایسه‌ی دوباره آیتم هایی که یک بار مقایسه شدن جلوگیری بشه. به این شکل

for($key = 0, $length = count($arr); $key < $length; $key++){          
    for($innerKey = $key + 1; $innerKey < $length; $innerKey++){
      //↑ Skipping the previous values and the value itself    
    }               
}

خب، نوبت میرسه به ساختن یک شرط که مقایسه هر دو آیتم رو انجام میده و باید توی لوپ (حلقه) داخلی قرار بگیره. یک همچین چیزی باید باشه:

if( ($diff = abs($arr[$keys[$key]] - $arr[$keys[$innerKey]])) < $nearest)

و نتیجه کلی میشه کوچیکترین تفاضلی که ما پیدا می کنیم و یک همچین چیزی میشه:

$result = [$arr[$keys[$key]], $arr[$keys[$innerKey]]];
$nearest = $diff;

کد کامل:

<?php

    $arr = [20, 1, 5, 10, 7, 16];

    $keys = array_keys($arr);
    $nearest = max($arr) - min($arr) + 1;
    $result = [];

    for($key = 0, $length = count($arr); $key < $length; $key++){

        for($innerKey = $key + 1; $innerKey < $length; $innerKey++){

            if( ($diff = abs($arr[$keys[$key]] - $arr[$keys[$innerKey]])) < $nearest){
                $result = [$arr[$keys[$key]], $arr[$keys[$innerKey]]];
                $nearest = $diff;

            }

        }

    }

    print_r($result);
    //=> [5, 7]       

?>

نمونه عملی

به نظر من در اینجا بهترین گزینه استفاده از پی اچ پی usort است که توسط quicksort پیاده سازی شده:

به این صورت:

$arr = array (20, 1, 5, 10, 7, 16);
   $temp=array();      
   for ($i = 0; $i < count($arr)-1; $i++)   
    {
        $diff=0;
        for ($j = $i+1; ($j < count($arr) && $i!=$j); $j++)
        {
            $diff=abs($arr[$i]-$arr[$j]);     //finding difference &taking absolute 
            $temp[] = array($arr[$i],$arr[$j], $diff); 
        }
    }
    usort($temp,function ($a, $b) { return $b[2] < $a[2]; });//sort `$temp[]` in ascending order according to the difference value
    list($x,$y,$d) = $temp[0];   //the first row of `$temp` contains values with the diff. is lowest 
                                //and the values is stored to `$x` & `$y` and there difference in `$d`
    echo "Related Values are $x and $y by $d";

اینم از یک دمو. خلاصه اگه بخوام بگم اینطوری کار می کنه:

بعد از گرفتن $temp[]، به صورت صعودی مرتب میشه بر اساس اختلاف ها. اولین سطر از $temp[] دقیقا نتیجه ای که ما به دنبالش هستیم رو داره.