Grouping an Array by Comparing 2 Adjacent Elements

Grouping an array by comparing 2 adjacent elements

Following Jan Dvorak's suggestion, this solution uses slice_before and a hash to keep the state:

class GroupByAdjacentDifference < Struct.new(:data)
  def group_by(difference)
    initial = { prev: data.first }

    data.slice_before(initial) do |item, state|
      prev, state[:prev] = state[:prev], item
      value_for(item) - value_for(prev) > difference
    end.to_a
  end

  def value_for(elem)
    elem.attribute
  end
end

require 'rspec/autorun'

describe GroupByAdjacentDifference do

  let(:a) { double("a", attribute: 1) }
  let(:b) { double("b", attribute: 3) }
  let(:c) { double("c", attribute: 6) }
  let(:d) { double("d", attribute: 9) }
  let(:e) { double("e", attribute: 10) }

  let(:data) { [a, b, c, d, e] }
  let(:service) { described_class.new(data) }

  context "#group_by" do
    it "groups data by calculating adjacent difference" do
      expect(service.group_by(2)).to eq([[a, b], [c], [d, e]])
    end
  end
end

which gives

$ ruby group_by_adjacent_difference.rb
.

Finished in 0.0048 seconds
1 example, 0 failures

In alternative, local variables could also be used to keep state, although I find it a bit harder to read:

class GroupByAdjacentDifference < Struct.new(:data)
  def group_by(difference)
    tmp = data.first

    data.slice_before do |item|
      tmp, prev = item, tmp
      value_for(item) - value_for(prev) > difference
    end.to_a
  end

  def value_for(elem)
    elem.attribute
  end
end

Ruby / Rails Group Array Based on Comparing Adjacent Elements

Here's one way using Enumerable#sort_by and Enumerable#slice_when. It requires Ruby 2.2+, though.

require 'time' # for sorting times

a = [{ name: "joe",   start: "9am",  end: "10am" },
     { name: "joe",   start: "10am", end: "11am" },
     { name: "harry", start: "11am", end: "12pm" },
     { name: "harry", start: "12pm", end: "1pm"  },
     { name: "harry", start: "2pm",  end: "3pm"  },
     { name: "joe",   start: "3pm",  end: "4pm"  },
     { name: "joe",   start: "4pm",  end: "5pm"  }]

a.sort_by { |h| [ h[:name], Time.parse(h[:start]) ] }                     # 1
 .slice_when { |x, y| x[:end] != y[:start] || x[:name] != y[:name] }.to_a # 2

which yields

=> [[{:name=>"harry", :start=>"11am", :end=>"12pm"}, {:name=>"harry", :start=>"12pm", :end=>"1pm"}],
    [{:name=>"harry", :start=>"2pm", :end=>"3pm"}],
    [{:name=>"joe", :start=>"9am", :end=>"10am"}, {:name=>"joe", :start=>"10am", :end=>"11am"}],
    [{:name=>"joe", :start=>"3pm", :end=>"4pm"}, {:name=>"joe", :start=>"4pm", :end=>"5pm"}]]

Here's a step-by-step explanation with intermediate results:

1) Sort the hashes by name and then by time within name. Note the use of Time.parse to temporarily convert your time string into a Time object for proper sorting:

 => [{:name=>"harry", :start=>"11am", :end=>"12pm"},
     {:name=>"harry", :start=>"12pm", :end=>"1pm"},
     {:name=>"harry", :start=>"2pm", :end=>"3pm"},
     {:name=>"joe", :start=>"9am", :end=>"10am"},
     {:name=>"joe", :start=>"10am", :end=>"11am"},
     {:name=>"joe", :start=>"3pm", :end=>"4pm"},
     {:name=>"joe", :start=>"4pm", :end=>"5pm"}]

2) Now slice this intermediate array when the end time of the former is not equal to the start time of the latter or when the names don't match using Daniel Polfer's solution. This returns an Enumerator object, hence the final to_a method call:

=> [[{:name=>"harry", :start=>"11am", :end=>"12pm"}, {:name=>"harry", :start=>"12pm", :end=>"1pm"}],
    [{:name=>"harry", :start=>"2pm", :end=>"3pm"}],
    [{:name=>"joe", :start=>"9am", :end=>"10am"}, {:name=>"joe", :start=>"10am", :end=>"11am"}],
    [{:name=>"joe", :start=>"3pm", :end=>"4pm"}, {:name=>"joe", :start=>"4pm", :end=>"5pm"}]]

If your hashes are already presorted, then Daniel Polfer's solution should work fine. But if you have any data where names and/or start times are out of order like this:

b = [{:name=>"joe", :start=>"3pm", :end=>"4pm"},
     {:name=>"bill", :start=>"2pm", :end=>"3pm"},
     {:name=>"joe", :start=>"5pm", :end=>"6pm"},
     {:name=>"joe", :start=>"4pm", :end=>"5pm"}] 

Just using slice_when returns

=> [[{:name=>"joe", :start=>"3pm", :end=>"4pm"}],
    [{:name=>"bill", :start=>"2pm", :end=>"3pm"}],
    [{:name=>"joe", :start=>"5pm", :end=>"6pm"}],
    [{:name=>"joe", :start=>"4pm", :end=>"5pm"}]]

instead of

=> [[{:name=>"bill", :start=>"2pm", :end=>"3pm"}],
    [{:name=>"joe", :start=>"3pm", :end=>"4pm"},
     {:name=>"joe", :start=>"4pm", :end=>"5pm"},
     {:name=>"joe", :start=>"5pm", :end=>"6pm"}]]

Best way to group adjacent array items by value

You can use Array.prototype.reduce method:

var result = [5, 5, 3, 5, 3, 3].reduce(function(prev, curr) {    if (prev.length && curr === prev[prev.length - 1][0]) {        prev[prev.length - 1].push(curr);    }    else {        prev.push([curr]);    }    return prev;}, []);
alert( JSON.stringify(result) );

How to compare adjacent elements in 2D array if duplicate?

You can use a simple for loop iterating over each array except the last and checking if the first element of the current iterated element matches the first element of current+1.

If they match, sum the third elements of each and assign to the current iterated array, delete current+1 (here using splice()) and decrement i to recheck the same index again.

var arr1 = [
  ['Egypt', 'Grid', 50],
  ['Egypt', 'Grid', 10],
  ['Nigeria', 'Grid', 20],
  ['Ghana', 'Grid', 60],
  ['Egypt', 'Grid', 30],
];

for (let i = 0; i < arr1.length - 1; i++) {
  if (arr1[i][0] === arr1[i + 1][0]) {
    arr1[i][2] = arr1[i][2] + arr1[i + 1][2];
    arr1.splice(i + 1, 1);
    i--;
  }
}

console.log(arr1);

Comparing adjacent elements in an array and selecting the smaller of each pair

The algorithm you've shown doesn't make much sense given the problem description of adjacent pairs. There's no reason for a nested loop in addition to break unless the intent is to compare each element to all of its previous elements, in which case it's correct. Either way, unshift is much slower than push and I see no reason to resort to this function regardless of the algorithm, nor do I see the reasoning behind the reversed outer loop.

I'd write the function for adjacent pairs using map. We can do this in one iteration.

const arrayPreviousLess = a => a.map((e, i) => a[i-1] < e ? a[i-1] : -1);
[  [3, 5, 2, 4, 5],  [1],  [1, 2],  [2, 1],  [1, 2, 3],  [3, 2, 1],  [3, 2, 3],  [3, 1, 6, 4, 5],].forEach(e => console.log(`[${e}] => [${arrayPreviousLess(e)}]`));

Grouping consecutive elements together using Javascript

You can use a counter variable which has to be incremented and the difference between the index and the consecutive elements are the same, group them in a temporary array. If the difference is varies for two consecutive array elements, the temporary element has to be moved to the result and the temporary array has to be assigned a new array object.

var array = [2, 3, 4, 5, 8, 9, 12, 13, 14, 15, 16, 17, 20];

var result = [], temp = [], difference;
for (var i = 0; i < array.length; i += 1) {
    if (difference !== (array[i] - i)) {
        if (difference !== undefined) {
            result.push(temp);
            temp = [];
        }
        difference = array[i] - i;
    }
    temp.push(array[i]);
}

if (temp.length) {
    result.push(temp);
}

console.log(result);
# [ [ 2, 3, 4, 5 ], [ 8, 9 ], [ 12, 13, 14, 15, 16, 17 ], [ 20 ] ]

groupBy function which groups non-adjacent elements

For now I cannot imagine general groupBy function that would work faster than O(n^2) time, but you may use something like this

groupBy2 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy2 = go [] where
  go acc comp [] = acc
  go acc comp (h:t) =
    let (hs, nohs) = partition (comp h) t
    in go ((h:hs):acc) comp nohs

It works exactly like regular groupBy, but it joins non-adjacent element classes.

However, if you are going to use on function the problem becomes a bit simplier, as we may use it's result as key for a map:

import qualified Data.Map as M

groupOn :: (Ord b) => (a -> b) -> [a] -> [[a]]
groupOn f =
  let unpack = fmap snd . M.toList
      fld m a = case M.lookup (f a) m of
        Nothing -> M.insert (f a) [a] m
        Just as -> M.insert (f a) (a:as) m
  in unpack . foldl fld M.empty

This is more efficient equivalent of

groupOn' f = groupBy2 ((==) `on` f)

(modulo ordering)

And btw – triplets and pairs already have defined Ord instance, you may compare them just like Ints

Re-ordering an array so it is grouped by identical elements

So the answer is no. This information doesn't really help. It may get you a little better, but not in big O.

To everyone who suggested hashing to get linear time, you can just as well do the same for sorting. This method is called radix/hash sort. It blows up your memory usage.

When there are more restrictions, you can even use cooler tricks (i.e. sum, xor, etc.)

However, for an algorithm that uses comparison only on a generalized array, you're not buying much by reducing the problem this way.

To give a simple intuition for this, suppose you have 1 redundancy for each element, so your array is a1,a1,...an,an (total of 2n elements of n unique numbers).

The size of the solution space is n! (so long as aj-aj are paired, you can permute the pair anyway you want as specified in your problem statement). The size of the input space is (2n)!/(2^(n)).

This means your algorithm needs to produce enough information to arrange ((2n)!/n!)/(2^n) = (n*(n+1)*...2n)/(2^n) elements. Each comparison gives you 1 bit of information. The number of required comparison iterations is log(n)+log(n+1)...+log(2n)-n which is big_omega(nlog(n)). This is not better or worse than sorting.

Here's a semi-rigorous treatment for sorting:
http://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf

I can probably be bribed to generate a similar proof for the current question.

Group same elements in JS array, but only when consecutive

You can do that with the reduce method.

const data = [  { message: "One", user: "Bob" },  { message: "Two", user: "Bob" },  { message: "Three", user: "Bob" },  { message: "Hello", user: "Sam" },  { message: "Hello", user: "Bob" },  { message: "Hello", user: "Sam" },  { message: "Hello", user: "Sam" }];
const result = data.reduce((acc, value) => {  // compare the current value with the last item in the collected array  if (acc.length && acc[acc.length - 1][0].user == value.user) {    // append the current value to it if it is matching    acc[acc.length - 1].push(value);  } else {    // append the new value at the end of the collected array    acc.push([value]);  }
  return acc;}, []);  console.log(result);

---

Related Topics