CODEWITHSUNDEEP
algorithmlist
Granitas
Granitas

Reputation: 300

algorithm for checking close by numbers for similarities in a list

I have a list and I need to find and extract all numbers in close proximity to a new list.

for example I have a list:

1,5,10,8,11,14,15,11,14,1,4,7,5,9

so if I want to extract all numbers that are close by 3(only 3, the gap must be 3, so 11,14 is correct, 11,13 is not.) near each other how can I design this without hard-coding the whole thing?

the result should look like: 8,11,14,11,14,1,4,7

This doesn't look too hard ,but I'm kind stuck, all I can come up with is a loop that checks n+1 member of the loop if it's more than n by 3 and include the n+1 member in a new list, however I don't know how to include the n member without making it appear on the new list twice if there is a string of needed numbers.

any ideas?

Upvotes: 3

Views: 165

Answers (5)

גלעד ברקן
גלעד ברקן

Reputation: 23955

And a Haskell version:

f g xs = dropWhile (null . drop 1) $ foldr comb [[last xs]] (init xs) where
  comb a bbs@(b:bs) 
    | abs (a - head b) == g = (a:head bbs) : bs
    | otherwise = 
        if null (drop 1 b) then [a] : bs else [a] : bbs

Output:

*Main> f 3 [5,10,8,11,14,15,11,14,1,4,7,5,9]
[[8,11,14],[11,14],[1,4,7]]

*Main> f 5 [5,10,8,11,14,15,11,14,1,4,7,5,9]
[[5,10]]

Upvotes: 0

Fred Foo
Fred Foo

Reputation: 363577

Just loop through the list, checking the next and previous element, and save the current one if it differs by 3 from either one. In Python, that's

>>> l = [1,5,10,8,11,14,15,11,14,1,4,7,5,9]
>>> # pad with infinities to ease the final loop
>>> l = [float('-inf')] + l + [float('inf')]
>>> [x for i, x in enumerate(l[1:-1], 1)
...  if 3 in (abs(x - l[i-1]), abs(x - l[i+1]))]
[8, 11, 14, 11, 14, 1, 4, 7]

Upvotes: 2

Fallen
Fallen

Reputation: 4565

A simple C++ code below:

assuming ar is the array of the initial integers and mark is a boolean array

for(int i=1;i<N;i++){
     if(ar[i]-ar[i-1]==3){
         mark[i]=1;
         mark[i-1]=1;
     }
}

Now to print the interesting numbers,

for(int i=0;i<N;i++){
    if(mark[i]==1)cout<<ar[i]<<" ";
}

The idea behind the implementation is, we mark a number as interesting if the difference from it to its previous one is 3 or if the difference between it and its next number is 3.

Upvotes: 1

High Performance Mark
High Performance Mark

Reputation: 78316

In Matlab

list = [1,5,10,8,11,14,15,11,14,1,4,7,5,9]

then

list(or([diff([0 diff(list)==3]) 0],[0 diff(list)==3]))

returns

8    11    14    11    14     1     4     7

For those who don't understand Matlab diff(list) returns the first (forward) differences of the elements in list. The expression [0 diff(list)] pads the first differences with a leading 0 to make the result the same length as the original list. The rest should be obvious.

In a nutshell: take forward differences and backward differences, select the elements where either difference is 3.

Upvotes: 1

No Idea For Name
No Idea For Name

Reputation: 11577

that's a single loop:

public List<int> CloseByN(int n, List<int> oldL)
{
   bool first = true;
   int last = 0;
   bool isLstAdded = false;
   List<int> newL = new List<int>();
   foreach(int curr in oldL)
   {
      if(first)
      {
         first = false;
         last = curr;
         continue;
      }
      if(curr - last == n)
      {
         if(isLstAdded == false)
         {
           newL.Add(last);
           isLstAdded = true;
         }
         newL.Add(curr);
      }
      else
      {
         isLstAdded = false;
      }
      last = curr;
   }
   return newL;
}

tested on your input and got your output

Upvotes: 0

Related Questions