CODEWITHSUNDEEP
algorithmlanguage-agnosticnumbersgrouping
tobawo
tobawo

Reputation: 83

Generating groups of numbers next to each other

I'm seraching for an algorithm to solve the following problem:

I have a set of Numbers 

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

and I want to group the Numbers that are next to each other (differ by x)

For example x=10 should output:

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

Unfortunately, I have no idea how to do it.

Edit: I have a lot of starting ideas. The algorithm doesn't have to be efficient, just working is okay.

One of them is:

- 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)

What do you think?

Upvotes: 3

Views: 119

Answers (1)

Alex Reinking
Alex Reinking

Reputation: 19846

Here's my first shot (from the comments). I'll edit this post as I get better ideas.

Algorithm:

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.

Example:

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]]

Since I noticed you were using PHP, here's an implementation in 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;
}

Upvotes: 3

Related Questions