How to Summarize Array of Integers as an Array of Ranges

How do I summarize array of integers as an array of ranges?

Functional approach using Enumerable#chunk:

ranges = [1, 2, 4, 5, 6, 7, 9, 13]
.enum_for(:chunk) # .chunk for Ruby >= 2.4
.with_index { |x, idx| x - idx }
.map { |_diff, group| [group.first, group.last] }

#=> [[1, 2], [4, 7], [9, 9], [13, 13]]

How it works: once indexed, consecutive elements in the array have the same x - idx, so we use that value to chunk (grouping of consecutive items) the input array. Finally we just need to take the first and last elements of each group to build the pairs.

How to summarize an array of integers to a string with ranges?

Another possible solution for positive numbers in ascending order. It features Array.prototype.reduce.

var array = [1, 2, 3, 5, 7, 9, 10, 11, 12, 15, 23, 24],

result = [];

array.reduce(function (r, a) {

result.push(r + 1 - a ? String(a) : result.pop().split('-')[0] + '-' + String(a));

return a;

}, array[0]);

document.write('<pre>' + JSON.stringify(result, 0, 4) + '</pre>');

Sum of range in array

Remove the first line of your function sumOfRange() var numbers = [1,-1,1,-1,1] because you are re-initializing the value of numbers, you need to use to array that is passed to the function when it is called.

function sumOfRange(numbers) {

var sum = 0;

for (var i = 0; i < numbers.length; i++) {

sum += numbers[i];

}

return sum;

}

console.log(sumOfRange([1,-1,1,-1,1]));

console.log(sumOfRange([1,2,3,4,5]));

console.log(sumOfRange([-4,-5,-10,0]));

How do I find the largest range of integers in a array?

You need to sort your data, then get what ranges are possible in the sorted data - then get the biggest range from it.

You should accumulate all found ranges and find the biggest one from it. Using your code:

def largestRange(array):
array.sort()
initial = array[0]
last_idx = final
size = (final - initial + 1)

ran = [] # collect ranges
for i in range(1,len(array)):
if array[i] - array[i-1] == 1 and i < len(array) - 1:
final += 1
elif array[i] - array[i-1] == 1 and i == len(array) - 1:
final += 1
ran.append( (initial, final) ) # add range
else:
ran.append( (initial, final) ) # add range
initial = array[i] # reset values
final = initial # reset values

# return the biggest found range
return max(ran, key=lambda n: n[1]-n[0])


data = [8, 4, 2, 10, 3, 6, 7, 9, 1]
print(largestRange(data))

gives [6,10].


I asked I have a list of numbers that are sometimes consecutive - how to get a list of ranges from it? 2 days ago, using my proposed solution for that problem you can solve yours

def get_consecutive_ranges(numbers: list[int]):
"""Takes an input of integers in a list, yields the
ranges of consecutive numbers that form the list."""
if not numbers:
return []

k = []
start,stop = None,None
for num in numbers:
if stop is None:
start, stop = num, num
elif stop == num-1:
stop += 1
else:
yield range(start,stop+1)
start, stop = num, num

yield range(start,stop+1)
data = [1, 11, 3, 0, 15, 5, 2, 4, 10, 7, 12, 6]
data.sort()

rg = get_consecutive_ranges(data)

# sort ranges by length ascending, take the last one
srg = sorted(rg, key=lambda g:len(g))[-1]
print([min(srg),max(srg))

to get to [0,7]. HTH.

Summing Array Elements from Specific Index Range

If you want to sum all the elements between two indexes, you can use a simple index based for loop.

let start = 1, end = 3, sum = 0;
for(let i = start; i <= end; i++)
sum += array[i];

slice and reduce can also be used:

let sum = array.slice(start, end+1).reduce((a,b)=>a+b,0);

If you just want the sum of the elements at two specific indexes, you can access the elements using bracket notation.

let sum = array[1]+array[3];

If you have an array of indexes to sum, you can loop over each index like so:

let indexes = [1, 3], sum = 0;
for(let index of indexes){
sum += array[index];
}

reduce can be used as well.

let indexes = [1, 3];
let sum = indexes.reduce((acc, cur)=>acc+array[cur],0);

Maximum Sum Elements in Range

One approach is to preprocess the numbers by splitting into non-overlapping arrays of length L (for L equal to different powers of 2).

Sort each array, and compute the cumulative sum of each array.

Then for each query, identify the arrays which combine to make the query range and use bisection to identify the level T such that if taking all elements above T we end up with a legal number of elements and the highest sum.

There will be log(N) arrays involved, and log(N) steps in each bisection, so this should be reasonably fast.

(Note if our first evaluation shows that taking all positive elements ends up with too many, we need to find the lowest legal level by bisection, while if we end up with too few we need to find the highest legal level by bisection)

Example

Suppose we have an array A = [ 1, -1, 2, -2, 3, -3, 4, 0 ].
The preprocessing will split it into:

Two arrays of length 4: [ 1, -1, 2, -2], [ 3, -3, 4, 0 ]
Four arrays of length 2: [ 1, -1], [2, -2], [ 3, -3], [4, 0 ]
Eight arrays of length 1: [1], [-1], [2], [-2], [ 3], [-3], [4], [0 ]

Then with a query 3 to 5, we want the elements [-2,3,-3] which we can form from the arrays [-2] and [3,-3].

Suppose we now want to find the maximum sum from at least 2 elements.

We first try taking all positive elements, this only results in 1 element so we know we need to bisect for the highest legal level.

The bisection could work by trying some values, e.g.

All elements >= 0 gives 1 element, so value is too high
All elements >= -4 gives 3 elements, so value is too low
All elements >= -2 gives 2 elements, so value is just right

How to sum values of ranges faster

Cumulative sum is probably what you are looking for, should be fast, since you sum just once and then just subtract.

import numpy as np

def max_sum(a, ranges):
maxi = -np.inf
cs = np.cumsum(a)
for el in ranges:
val = cs[el[1]] - (cs[el[0]-1] if el[0] > 0 else 0)
if val > maxi:
maxi = val
return maxi

EDIT:
if numpy is not allowed you can calculate cumsum by yourself for example with

cs = [a[0]]
for i in range(1, len(a)):
cs.append(cs[i-1] + a[i])

Ruby group integer array to range array

Yes.

Given that the original array is already sorted and uniqued:

[39, 40, 41, 42, 43, 44, 45, 49, 50, 51, 52]
.chunk_while{|i, j| i.next == j}
.map{|a| a.first..a.last}
# => [39..45, 49..52]


Related Topics



Leave a reply



Submit