Remove multiple ranges of values from array

Question

a1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
a2 = [2..4, 8..11, 16..17]

Removing one range of values from an array can be done like this:

[1, 2, 3, 4, 5, 6, 7, 8, 9].slice!(2..5)

Iterating over the ranges and apply the same as above (a2.each { |range| a1.slice!(range) }) isn't perfect though. The ranges overlap sometimes and thus destroy the referencing index for the other ranges.

So, any suggestions on how to remove the ranges in a2 from a1 in the most efficient way? a1 is normally [*0..10080] long. a2 has about 30 ranges, each containing hundreds of values.

I imagine if the ranges are in sorted order you could reverse the array and start slicing from the back working forward? — Jeff Price
– Jeff Price, Commented Aug 3, 2016 at 18:01
Heh! :) I actually just came to think of that possibility, but then I realized that the ranges will sometimes overlap. So it's still not a good solution. See update. — Fellow Stranger
– Fellow Stranger, Commented Aug 3, 2016 at 18:02

tadman · Accepted Answer · 2016-08-03 18:03:00Z

1

If the result of the first operation impacts the second you're either going to have to track the resulting offset implications, which can get crazy complicated, or simply go about doing the reverse operation and instead flag which you want or don't want using the ranges:

require 'set'

a1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
a2 = [2..4, 8..11, 16..17]

# Convert the ranges to a set of index values to remove
reject = Set.new(a2.flat_map(&:to_a))

# Using value/index pairs, accumulate those values which are
# not being excluded by their index.
a1.each_with_index.each_with_object([ ]) do |(v, i), a|
  a << v unless (reject.include?(i))
end

# => [0, 1, 5, 6, 7, 12, 13, 14, 15, 18, 19, 20]

answered Aug 3, 2016 at 18:03

tadman

212k23 gold badges237 silver badges266 bronze badges

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

6 Comments

Fellow Stranger Over a year ago

Excellent. But I assume the second part could be done like this equally well? a1 - reject.to_a

tadman Over a year ago

@FellowStranger Since a1 contains values and not offsets, no, you can't do that. You'd have to convert the ranges to values, and that also presumes that the values are unique, which they may not be.

fanta Over a year ago

but it could be like this a1 - a2.flat_map(&:to_a)

tadman Over a year ago

@fanta Again, this presumes the values in a1 are indicies and not random values.

Fellow Stranger Over a year ago

This doesn't work in cases where a1 doesn't start from 0. E.g. a1 = [*10..20]

|

Mladen Jablanović · Accepted Answer · 2016-08-03 19:15:36Z

0

[-1, *a2.flat_map(&:minmax), a1.length].each_slice(2).flat_map{|i,j| a1[i+1...j]}
# => [0, 1, 5, 6, 7, 12, 13, 14, 15, 18, 19, 20]

answered Aug 3, 2016 at 19:15

Mladen Jablanović

44.2k13 gold badges92 silver badges113 bronze badges

Comments

Eric · Accepted Answer · 2016-08-03 20:37:17Z

0

I'm not sure this is the least naive solution, but it seems simple to convert your ranges into arrays so you're dealing with like-for-like:

a2.each{ |a| a1 = a1 - a.to_a }

edited Aug 3, 2016 at 20:37

answered Aug 3, 2016 at 18:03

Eric

2,54918 silver badges23 bronze badges

2 Comments

tadman Over a year ago

(a) can be a here. Brackets are only necessary for raw ranges, like (0..1).to-a

Eric Over a year ago

So it can. Thanks!

Fellow Stranger · Accepted Answer · 2016-10-05 13:02:51Z

0

a1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
a2 = [2..4, 8..11, 16..17]

a1 - a2.flat_map(&:to_a)

answered Oct 5, 2016 at 13:02

Fellow Stranger

34.4k38 gold badges181 silver badges251 bronze badges

Collectives™ on Stack Overflow

Remove multiple ranges of values from array

4 Answers 4

6 Comments

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

6 Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related