How can I get the number of overlapping ranges in sorted order?

Question

Suppose I have an array of sorted inclusive ranges:

a = [1012..1014, 1016..1020, 1017..1022, 1021..1035, 1040..1080] 

I want the result to output an array of arrays, each of which the first element is a range and the second element is its overlapping counter, for example:

 [[1012..1014, 1], [1016..1016, 1], [1017..1020, 2], [1021..1022, 2], [1023..1035, 1], [1040..1080, 1]] 

For example, the range 1017..1020 included in the two ranges 1016..1020 and 1017..1022 , so its score will be equal to two.

Answer 1

code

 require 'set' def range_info(a) covered_by = a.each_with_object(Hash.new { |h,k| h[k]=Set.new }) { |r,h| r.each { |n| h[n] << r } } a.flat_map { |r| r.to_a }. uniq. slice_when { |b,c| c > b+1 }. flat_map { |r| r.to_a.slice_when { |b,c| covered_by[b] != covered_by[c] } }. flat_map { |enum| enum.to_a.map { |a| [a.first..a.last, covered_by[a.first].size] } } end 

Example

 a = [1012..1014, 1016..1020, 1017..1022, 1021..1035, 1040..1080] range_info(a) #=> [[1012..1014, 1], [1016..1016, 1], [1017..1020, 2], [1021..1022, 2], # [1023..1035, 1], [1040..1080, 1]] 

Explanation

First, create a covered_by hash with keys equal to numbers that are covered by at least one range in a , where covered_by[n] is equal to the set of all ranges in a that span the n key:

 covered_by = a.each_with_object(Hash.new { |h,k| h[k]=Set.new }) { |r,h| r.each { |n| h[n] << r } } #=> {1012=>#<Set: {1012..1014}>, 1013=>#<Set: {1012..1014}>, # ... # 1016=>#<Set: {1016..1020}>, 1017=>#<Set: {1016..1020, 1017..1022}>, # ... # 1079=>#<Set: {1040..1080}>, 1080=>#<Set: {1040..1080}>} 

See my answer here for an explanation of Hash.new { |h,k| h[k]=[] } Hash.new { |h,k| h[k]=[] } , which is similar to Hash.new { |h,k| h[k]=Set.new } Hash.new { |h,k| h[k]=Set.new } .

Next, we get an array of increasing non-overlapping ranges that span the same numbers that are covered by one or more ranges in a :

 arr = a.flat_map { |r| r.to_a }.uniq.slice_when { |b,c| c > b+1 } #=> [1012..1014, 1016..1035, 1040..1080] 

Then break each of the ranges in arr into counters that will generate arrays of consecutive numbers that are covered by the same ranges in a :

 b = arr.flat_map { |r| r.to_a.slice_when { |b,c| covered_by[b] != covered_by[c] } } #=> [#<Enumerator: #<Enumerator::Generator:0x007fd1ea854558>:each>, # #<Enumerator: #<Enumerator::Generator:0x007fd1ea8543c8>:each>, # #<Enumerator: #<Enumerator::Generator:0x007fd1ea854238>:each>] 

We can see the elements of b by converting them into arrays:

 b.map(&:to_a) #=> [[[1012, 1013, 1014]], # [[1016], [1017, 1018, 1019, 1020], [1021, 1022], # [1023, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033, # 1034, 1035]], # [[1040, 1041, 1042, 1043, 1044, 1045, 1046, 1047, 1048, 1049, 1050, # 1051, 1052, 1053, 1054, 1055, 1056, 1057, 1058, 1059, 1060, 1061, # 1062, 1063, 1064, 1065, 1066, 1067, 1068, 1069, 1070, 1071, 1072, # 1073, 1074, 1075, 1076, 1077, 1078, 1079, 1080]]] 

Finally, flat_map these arrays of arrays containing the range and the number of ranges in a that span all the elements of the range:

 c = b.flat_map { |enum| enum.to_a.map { |a| [a.first..a.last, covered_by[a.first].size] } } #=> [[1012..1014, 1], [1016..1016, 1], [1017..1020, 2], [1021..1022, 2], # [1023..1035, 1], [1040..1080, 1]] 

Answer 2

Here is my question on this issue. It may be inefficient - O (n ² ) complexity - however, this is a solution.

My approach is to determine if a range is a subrange of another range, follow these steps:

• Convert both ranges to an array and join, and then use the Array#|
• Sort an array obtained by combining two ranges.
• If one range is a subrange of another, then the range that includes the subrange will be equal to the combined sorted array when converted to an array using to_a .

Here is an illustration:

 r1 = 2..3 r2 = 1..4 pa = r1.to_a | r2.to_a #=> [2, 3, 1, 4] pa = a.sort #=> [1, 2, 3, 4] pa == r1.to_a #=> [1,2,3,4] == [2,3] #=> false pa == r2.to_a #=> [1,2,3,4] == [1,2,3,4] #=> true 

Based on the approach above, here is the complete code. Although I'm not sure that the list of example ranges asked in the question has any overlapping ranges, so I took an example of my own.

 h = {} r_a = [1016..1020, 1017..1020, 1021..1035, 1040..1080] r_a.each {|r| h[r] = 1} (0...r_a.length).each do |i| (0...r_a.length).each do |j| if (i != j) range_outer = r_a[i] range_inner = r_a[j] first,*rest,last = (range_outer.to_a | range_inner.to_a).to_a.sort combined_range = Range.new(first, last) if range_inner == combined_range h[range_outer] += 1 end end end end ph #=> {1016..1020=>1, 1017..1020=>2, 1021..1035=>1, 1040..1080=>1} 

Answer 3

The following solution works in limited cases: when the minimum range value and the maximum range value never match. (Ie, if x..100 exists, then there is no 100..y . Also there is no z..z .)

 break_points = a.flat_map{|r| [r.min - 1, r.min, r.max, r.max + 1]}.uniq.sort a.flat_map do |r| break_points .select{|i| r.min <= i and i <= r.max} .each_slice(2) .map{|min, max| min..max} end .group_by(&:itself) .map{|k, v| [k, v.length]} 

Answer 4

If you want to check all the subranges from the presented ranges, you can try something like this (only accounts for the subranges starting with the minimum value for each source range):

 a = [1012..1014, 1016..1020, 1017..1022, 1021..1035, 1040..1080] test_inputs = a.each_with_object([]) do |original, expanded| original.size.times.each{ |i| expanded << Range.new(original.min, original.min+i) } end output = test_inputs.each_with_object([]) do |input, result| appears = a.select{|x| x.min <= input.min}.select{|x| x.max >= input.max}.count result << [input, appears] end 

Answer 5

This is my approach to solving your problem. Let be

 a = [1012..1014, 1016..1020, 1017..1022, 1021..1035, 1040..1080] 

Step 1: Smooth this array, then count each element

 b = a.map(&:to_a).inject(:+).sort.group_by{|i| i }.map{|k,v| [k,v.count] } # => [[1012, 1], [1013, 1], [1014, 1], [1016, 1], [1017, 2], [1018, 2], [1019, 2], [1020, 2], [1021, 2], [1022, 2], [1023, 1], ... 

Step 2: Add Zero As Breakpoints

 c = b.each_with_index do |e, i| if e.nil? || b[i+1].nil? then next end if b[i][0] + 1 != b[i+1][0] || b[i][1] != b[i+1][1] then b.insert(i+1,nil) end end # => [[1012, 1], [1013, 1], [1014, 1], nil, [1016, 1], nil, [1017, 2], [1018, 2], [1019, 2], [1020, 2], [1021, 2], [1022, 2], nil, [1023, 1], ... 

Step 3: Divide the resulting array into breakpoints and group them into ranges

 d = c.split{|e| e.nil?}.map{|e| [(e.first[0]..e.last[0]), e.first[1]]} # => [[1012..1014, 1], [1016..1016, 1], [1017..1022, 2], [1023..1035, 1], [1040..1080, 1]] 

Update:

Since split is a method from Rails, so I have an alternative with pure Ruby.

Step 1: as above

Step 2: Divide the array into small groups as shown below

 c = [] j = 0 b.each_with_index do |e, i| if c[j].nil? then c[j] =[] end c[j] << b[i] if b[i+1] && (b[i][0] + 1 != b[i+1][0] || b[i][1] != b[i+1][1]) then j+=1 end end # pc => [ # [[[1012, 1], [1013, 1], [1014, 1]], # [[1016, 1]], # [[1017, 2], [1018, 2], [1019, 2], [1020, 2], [1021, 2], [1022, 2]], # ... # ] 

Step 3: Convert Each Group To A Range

 d = c.map{|e| [(e.first[0]..e.last[0]), e.first[1]]} # => [[1012..1014, 1], [1016..1016, 1], [1017..1022, 2], [1023..1035, 1], [1040..1080, 1]]