How do you combine consecutive repeating elements in an array?

Question

I need to combine consecutive repeating elements in an array, so that

[1, 2, 2, 3, 1] 

becomes

 [1, 2, 3, 1] 

#uniq does not work for this purpose. What for? Because #uniq produce this:

 [1, 2, 3] 

Answer 1

 def remove_consecutive_duplicates(xs) [xs.first] + xs.each_cons(2).select do |x,y| x != y end.map(&:last) end remove_consecutive_duplicates([1, 2, 2, 3, 1]) #=> [1,2,3,1] 

This returns a new array, such as uniq , and works in O(n) .

Answer 2

There is an abstraction in the kernel that pretty much does this job, Enumerated # chunk :

 xs = [1, 2, 2, 3, 3, 3, 1] xs.chunk { |x| x }.map(&:first) #=> [1, 2, 3, 1] 

Answer 3

Answer

sepp2k is already accepted, but here are a few alternatives:

 # Because I love me some monkeypatching class Array def remove_consecutive_duplicates_2 # Because no solution is complete without inject inject([]){ |r,o| r << o unless r.last==o; r } end def remove_consecutive_duplicates_3 # O(2n) map.with_index{ |o,i| o if i==0 || self[i-1]!=o }.compact end def remove_consecutive_duplicates_4 # Truly O(n) result = [] last = nil each do |o| result << o unless last==o last = o end result end end 

Although performance is not everything, here are a few tests:

 Rehearsal -------------------------------------------- sepp2k     2.740000   0.010000   2.750000 (  2.734665) Phrogz_2   1.410000   0.000000   1.410000 (  1.420978) Phrogz_3   1.520000   0.020000   1.540000 (  1.533197) Phrogz_4   1.000000   0.000000   1.000000 (  0.997460) ----------------------------------- total: 6.700000sec               user     system      total        real sepp2k     2.780000   0.000000   2.780000 (  2.782354) Phrogz_2   1.450000   0.000000   1.450000 (  1.440868) Phrogz_3   1.530000   0.020000   1.550000 (  1.539190) Phrogz_4   1.020000   0.000000   1.020000 (  1.025331) 

Tests are performed when duplicates are deleted with orig = (0..1000).map{ rand(5) } 10,000 times.

Answer 4

doesn't it work !uniq for what you do?

http://ruby-doc.org/docs/ProgrammingRuby/html/ref_c_array.html