Array of indexes to array of ranges

Question

Ranges in ruby are pretty cool. I end up with arrays such as this:

geneRanges = [(234..25), (500..510), (1640..1653)]

And subsequently have to remove bits of them. For that I:

genePositions = geneRanges.collect {|range| range.entries }.flatten
=> [500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 1640, 1641, 1642, 1643, 1644, 1645, 1646, 1647, 1648, 1649, 1650, 1651, 1652, 1653]

They get manipulated, so some numbers get excluded, and others may be added. I may end up with this:

[505, 506, 507, 600, 601, 602, 603, 1643, 1644, 1645, 1646, 1647, 1648, 1649, 1650, 1651, 1652, 1653, 1654]

How can I convert this back into a compact array of ranges? It seems that the inverse function should exist? I would expect it to return something like this:

[(505..507), (600..603), (1643..1654)]

Thanks!

more solutions on: stackoverflow.com/questions/12360108

tokland
– tokland

2012-09-10 22:49:35 +00:00
Commented Sep 10, 2012 at 22:49 — tokland
– tokland, Commented Sep 10, 2012 at 22:49
(234..25) is an invalid range. (234..25).to_a => [].

the Tin Man
– the Tin Man

2013-02-20 02:33:17 +00:00
Commented Feb 20, 2013 at 2:33 — the Tin Man
– the Tin Man, Commented Feb 20, 2013 at 2:33

Steve Weet · Accepted Answer · 2010-09-16 19:47:55Z

14

(New and improved. Stays fresh in your refrigerator for up to two weeks!):

a = [1, 2, 3, 10, 11, 20, 20, 4]

ranges = a.sort.uniq.inject([]) do |spans, n|
  if spans.empty? || spans.last.last != n - 1
    spans + [n..n]
  else
    spans[0..-2] + [spans.last.first..n]
  end
end

p ranges    # [1..4, 10..11, 20..20]

edited Sep 16, 2010 at 19:47

Steve Weet

28.5k11 gold badges72 silver badges86 bronze badges

answered Sep 16, 2010 at 16:59

Wayne Conrad

109k26 gold badges158 silver badges195 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Steve Weet Over a year ago

+1 Nice solution, however the value within the else should be spans[0..-2] + [spans.last.first..n] (Edited to fix)

Yannick Wurm Over a year ago

Excellent - thanks! Check also Steve Weet's generalization and Mladen Jablanović's response further down!

Wayne Conrad Over a year ago

Everyone in this place is smarter than I am, and @Mladen Jablanović consistently knocks them out of the park.

Andrew Grimm · Accepted Answer · 2013-09-12 02:19:02Z

8

Functional, not-very-readable solution:

(a[0,1]+a.each_cons(2).reject{|i,j| j-i==1}.flatten+a[-1,1]).
  each_slice(2).map{|i,j| i..j}

And a nice one:

class Array
  # splits array to sub-arrays wherever two adjacent elements satisfy a condition
  def split_by
    each_cons(2).inject([[first]]){|a, (i, j)|
      a.push([]) if yield(i, j)
      a.last.push j
      a
    }
  end

  # uses split_by to split array to subarrays with consecutive elements, then convert to range
  def to_range
    split_by{|i,j| j-i!=1}.map{|a| a.first..a.last}
  end
end

[505, 506, 507, 600, 1647, 1648, 1649, 1650, 1651, 1654].split_by{|i,j| j-i!=1}
#=> [[505, 506, 507], [600], [1647, 1648, 1649, 1650, 1651], [1654]]
[505, 506, 507, 600, 1647, 1648, 1649, 1650, 1651, 1654].to_range
#=> [505..507, 600..600, 1647..1651, 1654..1654]

edited Sep 12, 2013 at 2:19

Andrew Grimm

82.3k58 gold badges210 silver badges355 bronze badges

answered Sep 16, 2010 at 18:09

Mladen Jablanović

44.2k13 gold badges92 silver badges113 bronze badges

2 Comments

Andrew Grimm Over a year ago

SpaceBeforeModifierKeyword from RuboCop detected that there wasn't a space before if in a.push([])if yield(i, j). I didn't know that was valid Ruby. O_o

Andrew Grimm Over a year ago

Rubocop also suggests using each_with_object rather than inject.

Steve Weet · Accepted Answer · 2010-09-16 20:13:08Z

5

This is a straight crib of Wayne Conrads algorithm with a small tweak to make it work for other kinds of ranges, e.g. alphabetic

def array_to_ranges(a)
ranges = a.sort.uniq.inject([]) do |spans, n|
  if spans.empty? || spans.last.last.succ != n
    spans + [n..n]
  else
    spans[0..-2] + [spans.last.first..n]
  end
end
ranges
end

[
  [1..3, 10..11, 20..20, 4..4],
  [ "a".."c", "f".."h", "x".."z"],
  ["aa".."af"]
].each do |arange|
  p arange
  p array = arange.collect {|range| range.to_a}.flatten
  p array_to_ranges(array)
end

And the results of executing this are

[1..3, 10..11, 20..20, 4..4]
[1, 2, 3, 10, 11, 20, 4]
[1..4, 10..11, 20..20]
["a".."c", "f".."h", "x".."z"]
["a", "b", "c", "f", "g", "h", "x", "y", "z"]
["a".."c", "f".."h", "x".."z"]
["aa".."af"]
["aa", "ab", "ac", "ad", "ae", "af"]
["aa".."af"]

answered Sep 16, 2010 at 20:13

Steve Weet

28.5k11 gold badges72 silver badges86 bronze badges

1 Comment

the Tin Man Over a year ago

This is very cool. Imagine trying to do it in a language that didn't do duck-typing.

Community · Accepted Answer · 2017-05-23 12:34:02Z

Here's an answer (adapted from this code) that is more than twice as fast as the other code posted here. Further, only this answer and the one by @Steve handle arrays of non-integers.

class Array
  def to_ranges
    return [] if empty?
    [].tap do |ranges|
      init,last = first
      each do |o|
        if last && o != last.succ
          ranges << (init..last)
          init = o
        end
        last = o
      end
      ranges << (init..last)
    end
  end
end

Here are the benchmark results:

                 user     system      total        real
steve        1.107000   0.000000   1.107000 (  1.106221)
wayne        1.092000   0.000000   1.092000 (  1.099220)
user229426   0.531000   0.000000   0.531000 (  0.523104)
mladen1      0.780000   0.000000   0.780000 (  0.774154)
mladen2      0.780000   0.000000   0.780000 (  0.792159)
phrogz       0.218000   0.000000   0.218000 (  0.220044)

All benchmarked code was adapted to remove sort.uniq for a fair comparison.

Wayne Conrad · Accepted Answer · 2010-09-16 16:43:52Z

1

I've never seen anything in the Ruby language that does that, but here is some code that might help you do it yourself:

http://snippets.dzone.com/posts/show/4677

edited Sep 16, 2010 at 16:43

Wayne Conrad

109k26 gold badges158 silver badges195 bronze badges

answered Sep 16, 2010 at 16:34

coder_tim

1,7201 gold badge12 silver badges13 bronze badges

Comments

ghostdog74 · Accepted Answer · 2010-09-16 17:23:48Z

1

ar=[505, 506, 507, 600, 1647, 1648, 1649, 1650, 1651, 1654]
def to_range(a)
  s=a[0]
  a.each_cons(2) do |a|
    if a[1]-a[0]!=1
        p s .. a[0]
        s=a[1]
    end
  end
  left=a.index(s)
  p a[left..-1][0]..a[left..-1][-1]
end
to_range(ar)

answered Sep 16, 2010 at 17:23

ghostdog74

346k62 gold badges264 silver badges349 bronze badges

Comments

fl00r · Accepted Answer · 2011-05-09 21:32:29Z

0

array = [505, 506, 507, 600, 601, 602, 603, 1643, 1644, 1645, 1646, 1647, 1648, 1649, 1650, 1651, 1652, 1653, 1654]
array.inject([]){ |a, e| a[-1] && a[-1].last && a[-1].last == e-1 ? a[-1] = (a[-1].first..e) : a << (e..e); a }
#=> [505..507, 600..603, 1643..1654]

and for not sorted arrays you can presort it:

array.sort!.uniq!

answered May 9, 2011 at 21:32

fl00r

83.7k33 gold badges222 silver badges239 bronze badges

3 Comments

Jack Casey Over a year ago

~~You can't chain sort! !!!!~~ Sorry actually sort! does look like it is safe to chain for some reason. Most other mutating methods ending in ! aren't (like gsub!, uniq!, etc) So I just cringe when I see anyone using the return value of any method ending in !

fl00r Over a year ago

@JackCasey, of course you can chain any of listed methods (sort!, gsub! uniq!). But it could be meaningless in some cases

Jack Casey Over a year ago

Sure, I meant it's a trap sometimes :)

Collectives™ on Stack Overflow

Array of indexes to array of ranges

7 Answers 7

3 Comments

2 Comments

1 Comment

Comments

Comments

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

3 Comments

2 Comments

1 Comment

Comments

Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related