Partial sums with a twist (adding up to the previous element)

Question

I have an array of integers, say

a=[4, 6, 7, 2]

and I would like to produce a new array of the same size, with the following properties:

- The first array, b[0], is 0 - For the remaining elements, b[n] is the sum of all elements from a[0] up to a[n].

Hence, for a above, b should turn out as [0, 4, 10, 17].

Efficiency is not an issue (although I would like to reuse already caluclated partial sums, instead recalculate them again and again), but the result should be understandable in maintaiable.

I came up with the following solution:

b=[nil]*a.size ind=-1 b.map! {|i| (ind >= 0 ? (a[ind]+b[ind]) : 0).tap {ind+=1}};

This works, but I don't like it much, mostly because of the "backindex" variable ind and the need to preallocate b. I would like to have something like

b = a.map{ .... }

or similar. Does anybody have some idea of how to do it better?

There's map.with_index which moves that functionality to existing code. — Dave Newton
– Dave Newton, Commented Jun 3, 2020 at 14:14
@DaveNewton : I thought about it, but I would have then to calculate the one-off index inside the block, i.e. a.map_with_index {|i| ind=i-1;....}. — user1934428
– user1934428, Commented Jun 4, 2020 at 6:40
@Matt : Your solution is great!!!! Please make it an answer, and I will accept it. I just suggest renaming the block parameter a to, say, memo to avoid a warning that the local variable a is shadowing the outer variable a (if $VERBOSE is turned on). — user1934428
– user1934428, Commented Jun 4, 2020 at 6:44

Matt · Accepted Answer · 2020-06-04 12:01:31Z

You can use inject:

a.inject([0]) { |acc,x| acc << acc.last + x } => [0, 4, 10, 17, 19]

and then pop off the last element, from either the result or a before the call.

Yakov · Accepted Answer · 2020-06-03 14:45:20Z

This works, but it looks weird because you should call the input array inside the loop:

a.each_with_object([]).with_index do |(_, array), index| array << (index.zero? ? 0 : array[index - 1] + a[index - 1]) end

Jörg W Mittag · Accepted Answer · 2020-06-04 05:49:01Z

The general operation is called prefix sum or scan, and is available in many collection libraries … unfortunately not in Ruby's. There are some third-party gems that extend Ruby's collection libraries that have it, but it is not too hard to roll your own:

module EnumerableScanExtension def scan(init) return enum_for(__callee__) unless block_given? inject([[init], init]) do |(res, acc), el| acc = yield acc, el [res << acc, acc] end.first end end module EnumerableWithScan refine Enumerable do include EnumerableScanExtension end end using EnumerableWithScan [4, 6, 7, 2].scan(0) {|acc, el| acc + el } #=> [0, 4, 10, 17, 19]

[Note: Ideally, the implementation should fully mimic all the modes and overloads of inject; I left that out for brevity.]

Your desired result is then just a slight modification:

[4, 6, 7, 2].scan(0) {|acc, el| acc + el }[0...-1] #=> [0, 4, 10, 17]

An alternative would be to replace inject([[], init]) with inject([[init], init]), in which case [4, 6, 7, 2].scan(10) {|acc, el| acc + el } #=> [10, 14, 20, 27, 29] (rather than [14, 20, 27, 29]). I'm thinking that init would most often be wanted as the first element (which could always be drop(1)ed). An example would be when the method is used to convert a discrete PDF (probability density function) to a CDF (with 1.0 appended). One might also consider giving init a default value of zero.
Yes, that would bring it more in line with what other languages are doing. Ideally, it would implement the full protocol of inject but doing that in Ruby is incredibly annoying without method overloading or privileged internal access to the arguments list.
Great idea for a general solution, to enhance our library. For my concrete case, I feel that using incject directly, as proposed by Matt in his comment, is simpler and very readable.
There is a feature request to add such a method to Ruby bugs.ruby-lang.org/issues/17016 but the core team wants to be sure if it's useful

Collectives™ on Stack Overflow

Partial sums with a twist (adding up to the previous element)

3 Answers 3

Comments

Comments

4 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

4 Comments

Linked

Related