0

I've been using a piece of Ruby code that I found here.

Here's the code:

a = [1, 4, 7, 13]

def add(ary, idx, sum)
    (idx...ary.length).each do |i|
        add(ary, i+1, sum + ary[i])
    end
    puts sum
end
add(a, 0, 0)

Thing is, I don't need it to spit out the results of adding all the sums. I need the min, max, median, and average of the sums.

How do I modify this code in order to get them? I'm a total beginner at Ruby. I've been using this code, and then transferring the results to Excel to get the values I want. But it feels like my methods could be more efficient.

Thank you for your help.

EDIT: Expected results - Currently the code spits this out on my screen:

25
12
18
5
21
8
14
1
24
11
17
4
20
7
13
0

I want it to spit out the min, average, median, and max instead:

0
12.5
12.5
25
johnny
  • 1
  • 2
  • 1
    You need to specify - what do you mean by "All Possible Sums". P.S. Note that this code uses recursion - it is absolutely unnecessary in this straightforward task for simple loop. – MBo Mar 01 '18 at 16:17
  • I added expected results. I don't know what idx=sum=0 means. I just use it because it worked so far (after verifying manually). All possible sums here means that if I have a set of numbers (e.g., 1, 2, 3), the result should be another set of numbers for the results of 1, 1+2, 1+2+3, 2+3, 1+3...etc. until there are no more unused combinations. But I don't need the pile of numbers. I just need min, max, median, average. – johnny Mar 01 '18 at 16:20
  • I revised the expected results. – johnny Mar 01 '18 at 16:24
  • How many numbers do you have? Does this need to be efficient? And are your numbers all non-negative? – Stefan Pochmann Mar 01 '18 at 16:25
  • Stefan, all my numbers are non-negative. The quantity of numbers varies (these are for calculating pricing statistics of optional car model packages). It doesn't need to be efficient, just working. – johnny Mar 01 '18 at 16:27
  • 1
    Then just collect the sums instead of printing them and sort them. Min/max/mean/median of a sorted array are trivial. – Stefan Pochmann Mar 01 '18 at 16:29
  • I...don't know how to do that. I've thought I could modify the code myself, and Googled for instructions. But it seems like nothing I tried works. I'm unfamiliar with Ruby. – johnny Mar 01 '18 at 16:30
  • 1
    In Ruby you'd usually see something like `0.upto(a.size).flat_map { |i| a.combination(i).map(&:sum) }` – Stefan Mar 01 '18 at 16:38
  • Stefan, I apologize, but can you explain that like you're explaining it to a total idiot? I have no idea what that string of code does. – johnny Mar 01 '18 at 16:46
  • It returns an array containing all possible sums, basically like your example code above. – Stefan Mar 01 '18 at 17:06

4 Answers4

1
a = [1, 4, 7, 13]

def all_sums(array)
    combination_lengths = (0..array.length)
    all_combinations = combination_lengths.flat_map do |c|
      array.combination(c).to_a
    end
    all_combinations.map(&:sum)
end

def print_min_max_avg_med(array)
  puts array.min
  puts array.max
  puts array.sum.to_f / array.length
  sorted_arr = array.sort
  puts sorted_arr[(array.length - 1) / 2] + sorted_arr[array.length / 2] / 2.0
end

print_min_max_avg_med(all_sums(a))
A. Bronca
  • 11
  • 1
  • 4
  • Unfortunately I'm looking for something that works in general, not just this task. As mentioned in my comment elsewhere, this is for calculating pricing statistics of optional new car packages. There is no guarantee that there are an even number of packages, or odd. – johnny Mar 01 '18 at 17:42
  • @johnny Huh? This solution *does* work for all numbers of packages. If you're referring to my comment, that was specifically about the `print_min_max_avg_med ` function alone. – Stefan Pochmann Mar 01 '18 at 17:43
  • @StefanPochmann aside from the fact that it converts the median into a float, I think it should work for odd-length arrays. But yeah for this use-case the empty checks could probably be removed – A. Bronca Mar 01 '18 at 18:20
  • @StefanPochmann ah, yep you're right. I was looking at the wrong value. Fixing it now. – A. Bronca Mar 01 '18 at 18:26
  • The minimum and maximum *sums* are desired, not the minimum and maximum elements. If, for example, the array were `[1,-2,3,-4]` the minimum and maximum sums would be `-6` and `4`, respectively. Similar for the mean and median. – Cary Swoveland Mar 03 '18 at 01:12
0

Ok, instead of outputting the values we can store them in an arrary and use that array for the values you need. (edited after chewing out by Stefan Pochmann)

 a = [1, 4, 7, 13]

def add(ary, idx, sum, results = nil)
  unless results
    results = []
    first_run = true
  end
  (idx...ary.length).each do |i|
      add(ary, i+1, sum + ary[i], results)
  end
  results << sum

  if first_run
    puts results.min
    puts results.inject(&:+).to_f / results.size
    puts (results.sort[((results.size - 1) / 2)] + results.sort[(results.size / 2)]) / 2.0
    puts results.max
  end
end
add(a, 0, 0)
SteveTurczyn
  • 36,057
  • 6
  • 41
  • 53
0

Alright, after seeing the examples from Pochmann and Bronca, I put this together after googling for a better way to get the median.

a = [1, 4, 7, 13]

def all_sums(array)
    combination_lengths = (0..array.length)
    all_combinations = combination_lengths.flat_map do |c|
      array.combination(c).to_a
    end
    all_combinations.map(&:sum)
end

def median(array)
  sorted = array.sort
  len = sorted.length
  (sorted[(len - 1) / 2] + sorted[len / 2]) / 2.0
end

def print_min_max_avg_med(array)
  puts array.min
  puts array.empty? ? 0 : array.sum.to_f / array.length
  puts median(array)
  puts array.max
end

print_min_max_avg_med(all_sums(a))

I've run a few tests, and it seems to work for both odd and even arrays. Hope this is useful to the future somebody else stuck in my present position.

Thank you everyone who helped.

johnny
  • 1
  • 2
  • Baw... saying *"after googling for a better way to get the median"* got me excited for a moment. Because that's the only one I can't trivially do in linear time. But then I saw you don't actually do it differently but still the same exponential way. – Stefan Pochmann Mar 01 '18 at 18:08
  • Is there a downside to the way I'm doing it? I literally started looking at Ruby like 2 days ago after getting tired of the inaccuracy of estimation formulas I made for Excel. – johnny Mar 01 '18 at 18:11
  • Well the same "downside" as all ways proposed so far. It takes exponential time and space. If you had let's say 30 or more packages, you'd be in trouble. – Stefan Pochmann Mar 01 '18 at 18:15
  • Ah, I see. Well, thankfully it's unlikely that I'll run into an automaker offering 30 packages on a single model of vehicle. Even Audi has like 10 max. – johnny Mar 01 '18 at 18:25
  • Yeah, for ten this way is fine. You could still do [`min = 0`, `max = a.sum` and `average = a.sum / 2.0`](https://eval.in/965310), but if you're computing all sums anyway, you might as well just use them for that as well. – Stefan Pochmann Mar 01 '18 at 18:35
0

Min and Max

The min and max are easy.

def min_and_max_of_sums a
  return [nil, nil] if a.empty?      
  negs, nonnegs = a.partition { |n| n < 0 }
  [negs.any? ? negs.sum : nonnegs.min, nonnegs.any? ? nonnegs.sum : negs.max]
end

min_and_max_of_sums [1, 4, -5, 7, -8, 13]
  #=> [-13, 25]
min_and_max_of_sums [1, 2, 3]
  #=> [1, 6]
min_and_max_of_sums [-1, -2, -3]
  #=> [-6, -1]
min_and_max_of_sums []
  #=> [nil, nil]

Mean

Now consider the calculation of the mean.

If n is the size of the array a, there are 2n combinations of elements of a that contain between 0 and n elements.1 Moreover, there is a 1-1 mapping between each of those combinations and an n-vector of zeros and ones, where the ith element of the n-vector equals 1 if and only if the element ai is included in the combination. Note that there are 2n such n-vectors, one-half containing a 1 in the ith position. This means that one-half of the combinations contain the element ai. As i is arbitrary, it follows that each element of a appears in one-half of the combinations.

The mean of the sums of all elements of all combinations equals T/2n, where T is the sum of the sums of the elements of each combination. Each element ai appears in 2n/2 combinations, so its contribution to T equals (in Ruby terms)

a[i] * 2**(n)/2

As this hold for every element of a, the mean equals

a.sum * (2**(n)/2)/2**(n)
  => a.sum/2

Here's an example. For the array

a = [1, 4, 8]

the mean of the sums would be

a.sum/2
  #=> 13/2 => 6.5

If we were to calculate the mean by its definition we would perform the following calculation (and of course get the same return value).

(0 + (1) + (4) + (8) + (1+4) + (1+8) + (4+8) + (1=4+8))/2**3
  #=> (4*1 + 4*4 + 4*8)/8
  #=> (1 + 4 + 8)/2
  #=> 6.5

I will leave the calculating of the median to others.

1 Search for "Sums of the binomial coefficients" here.

Cary Swoveland
  • 106,649
  • 6
  • 63
  • 100