Создание группы номеров рядом друг с другом

Question

Я seraching для алгоритма для решения следующей задачи:

У меня есть набор чисел

(e.g 100,74,104,76,29,79,98,33,201) 

, и я хочу, чтобы сгруппировать цифры, которые рядом друг с другом (различаются х)

Например х = 10 следует вывести:

[(100,104,98) (74,76,79) (33,29) (201)] 

Unf К сожалению, я не знаю, как это сделать.

Редактировать: У меня много идей для начала. Алгоритм не должен быть эффективным, просто работа в порядке.

Один из них:

- A) Picking first number, comparing its size with all the other numbers 
- B) If the condition is complied, saving it in another set and deleting it from the input set 
- C) Select the next element that isn't deleted and Start at A (Proceed until input set is empty) 

Что вы думаете?

Answer 1

Вот мой первый выстрел (из комментариев). Я отредактирую этот пост, когда у меня появятся лучшие идеи.

Алгоритм:

Input (a) a list L (b) a number x, the maximum gap 
1) Sort the list 
2) Take as many elements from the list as you can without exceeding the gap 
3) Create a new group 
4) If there are no more elements in the list, you're done, otherwise to to step 2. 

Пример:

Input: L = [100,74,104,76,29,79,98,33,201], x = 10 
Sorted: [29, 33, 74, 76, 79, 98, 100, 104, 201] 
Output: [[29, 33], [74, 76, 79], [98, 100, 104], [201]] 

Так как я заметил, что вы использовали PHP, вот реализация в PHP:

function cluster($arr, $x) 
{ 
     $clusters = array(); 
     if(count($arr) == 0) 
       return $clusters; 

     sort($arr); 
     $curCluster[0] = array_shift($arr); 
     while(count($arr) > 0) { 
       $cur = array_shift($arr); 
       if($cur - $curCluster[0] < $x) 
         array_push($curCluster, $cur); 
       else { 
         array_push($clusters, $curCluster); 
         $curCluster = array($cur); 
       } 
     } 
     if(count($curCluster) != 0) 
       array_push($clusters, $curCluster); 
     return $clusters; 
}