Ruby, уменьшающий числовой массив в массив начального конца диапазона

У меня есть массив чисел, как показано ниже:

[11, 12, 13, 14, 19, 20, 21, 29, 30, 33]

Я хотел бы уменьшить этот массив до:

[[11,14], [19,21], [29,30], [33,33]]

Определите последующие числа в массиве и нажмите только начало и конец его диапазонов.

Как это сделать?

5 ответов

Реально какая-то проблема решается, чтобы привести пример метода slice_before в ruby ​​docs:

a = [0, 2, 3, 4, 6, 7, 9]
prev = a[0]
p a.slice_before { |e|
 prev, prev2 = e, prev
 prev2 + 1 != e
}.map { |es|
 es.length <= 2 ? es.join(",") : "#{es.first}-#{es.last}"
}.join(",")

В вашем случае вам нужно немного подстроить его:

a = [11, 12, 13, 14, 19, 20, 21, 29, 30, 33]
prev = a[0]
p a.slice_before { |e|
 prev, prev2 = e, prev
 prev2 + 1 != e
}.map { |es|
 [es.first, es.last]
}


Здесь другой способ, с использованием перечислителя с Enumerator # next и Перечислитель #peek. Он работает для любой коллекции, которая реализует succ (aka next).

код

def group_consecs(a)
 enum = a.each
 pairs = [[enum.next]]
 loop do
 if pairs.last.last.succ == enum.peek
 pairs.last << enum.next 
 else
 pairs << [enum.next]
 end
 end
 pairs.map { |g| (g.size > 1) ? g : g*2 }
end

Обратите внимание, что Enumerator # peek вызывает исключение StopInteration, если перечислитель enum уже в конце, когда вызывается enum.peek, Это исключение обрабатывается цикл ядрa > , который прерывает цикл.

<сильные> Примеры

a = [11, 12, 13, 14, 19, 20, 21, 29, 30, 33]
group_consecs(a)
 #=> [[11, 12, 13, 14], [19, 20, 21], [29, 30], [33, 33]]
a = ['a','b','c','f','g','i','l','m']
group_consecs(a)
 #=> [["a", "b", "c"], ["f", "g"], ["i", "i"], ["l", "m"]]
a = ['aa','ab','ac','af','ag','ai','al','am']
group_consecs(a)
 #=> [["aa", "ab", "ac"], ["af", "ag"], ["ai, ai"], ["al", "am"]]
a = [:a,:b,:c,:f,:g,:i,:l,:m]
group_consecs(a)
 #=> [[:a, :b, :c], [:f, :g], [:i, :i], [:l, :m]]

Создайте массив из семи объектов даты для примера, затем группируйте последовательные даты:

require 'date'
today = Date.today
a = 10.times.map { today = today.succ }.values_at(0,1,2,5,6,8,9)
 #=> [#<date: 2014-08-07="" ((2456877j,0s,0n),+0s,2299161j)="">,
 # #<date: 2014-08-08="" ((2456878j,0s,0n),+0s,2299161j)="">,
 # #<date: 2014-08-09="" ((2456879j,0s,0n),+0s,2299161j)="">,
 # #<date: 2014-08-12="" ((2456882j,0s,0n),+0s,2299161j)="">,
 # #<date: 2014-08-13="" ((2456883j,0s,0n),+0s,2299161j)="">,
 # #<date: 2014-08-15="" ((2456885j,0s,0n),+0s,2299161j)="">,
 # #<date: 2014-08-16="" ((2456886j,0s,0n),+0s,2299161j)="">]
group_consecs(a)
 #=> [[#<date: 2014-08-07="" ((2456877j,0s,0n),+0s,2299161j)="">,
 # #<date: 2014-08-08="" ((2456878j,0s,0n),+0s,2299161j)="">,
 # #<date: 2014-08-09="" ((2456879j,0s,0n),+0s,2299161j)="">
 # ],
 # [#<date: 2014-08-12="" ((2456882j,0s,0n),+0s,2299161j)="">,
 # #<date: 2014-08-13="" ((2456883j,0s,0n),+0s,2299161j)="">
 # ],
 # [#<date: 2014-08-15="" ((2456885j,0s,0n),+0s,2299161j)="">,
 # #<date: 2014-08-16="" ((2456886j,0s,0n),+0s,2299161j)="">
 # ]]
</date:></date:></date:></date:></date:></date:></date:></date:></date:></date:></date:></date:></date:></date:>


Это код, который я написал для проекта некоторое время назад:

class Array
 # [1,2,4,5,6,7,9,13].to_ranges # => [1..2, 4..7, 9..9, 13..13]
 # [1,2,4,5,6,7,9,13].to_ranges(true) # => [1..2, 4..7, 9, 13]
 def to_ranges(non_ranges_ok=false)
 self.sort.each_with_index.chunk { |x, i| x - i }.map { |diff, pairs|
 if (non_ranges_ok)
 pairs.first[0] == pairs.last[0] ? pairs.first[0] : pairs.first[0] .. pairs.last[0]
 else
 pairs.first[0] .. pairs.last[0]
 end
 }
 end
end
if ($0 == __FILE__)
 require 'awesome_print'
 ary = [1, 2, 4, 5, 6, 7, 9, 13, 12]
 ary.to_ranges(false) # => [1..2, 4..7, 9..9, 12..13]
 ary.to_ranges(true) # => [1..2, 4..7, 9, 12..13]
 ary = [1, 2, 4, 8, 5, 6, 7, 3, 9, 11, 12, 10]
 ary.to_ranges(false) # => [1..12]
 ary.to_ranges(true) # => [1..12]
end

Легко изменить это, чтобы возвращать пары start/end:

class Array
 def to_range_pairs(non_ranges_ok=false)
 self.sort.each_with_index.chunk { |x, i| x - i }.map { |diff, pairs|
 if (non_ranges_ok)
 pairs.first[0] == pairs.last[0] ? [pairs.first[0]] : [pairs.first[0], pairs.last[0]]
 else
 [pairs.first[0], pairs.last[0]]
 end
 }
 end
end
if ($0 == __FILE__)
 require 'awesome_print'
 ary = [1, 2, 4, 5, 6, 7, 9, 13, 12]
 ary.to_range_pairs(false) # => [[1, 2], [4, 7], [9, 9], [12, 13]]
 ary.to_range_pairs(true) # => [[1, 2], [4, 7], [9], [12, 13]]
 ary = [1, 2, 4, 8, 5, 6, 7, 3, 9, 11, 12, 10]
 ary.to_range_pairs(false) # => [[1, 12]]
 ary.to_range_pairs(true) # => [[1, 12]]
end


[Изменить: Ха! Я не понял этот вопрос. В вашем примере для массива

a = [11, 12, 13, 14, 19, 20, 21, 29, 30, 33]

вы указали желаемый массив пар:

[[11,14], [19,21], [29,30], [33,33]]

которые соответствуют следующим смещениям в a:

[[0,3], [4,6], [7,8], [9,9]]

Соответствующие пары охватывают первые 4 элемента, следующие 3 элемента, затем следующие 2 элемента и следующий элемент (по совпадению, очевидно). Я думал, что вам нужны такие пары, каждый с интервалом меньше предыдущего, а промежуток первого - как можно больше. Если вы быстро посмотрите на мои примеры ниже, мое предположение может быть более ясным. Оглядываясь назад, я не знаю, почему я не понял вопрос правильно (я должен был посмотреть на ответы), но там он у вас есть.

Несмотря на мою ошибку, я оставлю это, поскольку я нашел интересную проблему, и имел возможность использовать квадратичную формулу в решении.

Tide]

Вот как я это сделаю.

код

def pull_pairs(a)
 n = ((-1 + Math.sqrt(1.0 + 8*a.size))/2).to_i
 cum = 0
 n.downto(1).map do |i|
 first = cum
 cum += i
 [a[first], a[cum-1]]
 end
end

<сильные> Примеры

a = %w{a b c d e f g h i j k l}
 #=> ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"]
pull_pairs(a)
 #=> [["a", "d"], ["e", "g"], ["h", "i"], ["j", "j"]]
a = [*(1..25)]
 #=> [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
 # 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
pull_pairs(a)
 #=> [[1, 6], [7, 11], [12, 15], [16, 18], [19, 20], [21, 21]]
a = [*(1..990)]
 #=> [1, 2,..., 990]
pull_pairs(a)
 #=> [[1, 44], [45, 87],..., [988, 989], [990, 990]]

Объяснение

Сначала мы вычислим количество пар значений в массиве, который мы будем производить. Нам задан массив (выраженный алгебраически):

a = [a0,a1,...a(m-1)]

где m = a.size.

Учитывая n > 0, создаваемый массив:

[[a0,a(n-1)], [a(n),a(2n-2)],...,[a(t),a(t)]]

Эти элементы охватывают первые n+(n-1)+...+1 элементы a. Поскольку это арифметическая функция, сумма равна n(n+1)/2. Следовательно,

t = n(n+1)/2 - 1

Теперь t <= m-1, поэтому мы максимизируем количество пар в выходном массиве, выбирая самый большой n такой, что

n(n+1)/2 <= m

который является поплавковым решением для n в квадратичном выражении:

n^2+n-2m = 0

округляется до целого числа, которое

int((-1+sqrt(1^1+4(1)(2m))/2)

или

int((-1+sqrt(1+8m))/2)

Предположим, что

a = %w{a b c d e f g h i j k l}

Тогда m (=a.size) = 12, поэтому:

n = int((-1+sqrt(97))/2) = 4

и желаемый массив будет:

[['a','d'],['e','g'],['h','i'],['j','j']]

После вычисления n построение массива пар является простым.


Здесь элегантное решение:

arr = [11, 12, 13, 14, 19, 20, 21, 29, 30, 33]
output = []
# Sort array
arr.sort!
# Loop through each element in the list
arr.each do |element|
 # Set defaults - for if there are no consecutive numbers in the list
 start = element
 endd = element
 # Loop through consecutive numbers and check if they are inside the list
 i = 1
 while arr.include?(element+i) do
 # Set element as endd
 endd = element+i
 # Remove element from list
 arr.delete(element+i)
 # Increment i
 i += 1
 end
 # Push [start, endd] pair to output
 output.push([start, endd])
end

licensed under cc by-sa 3.0 with attribution.