I have a list of numbers (sorted ascending) and I want to halve the list several times, and combine neighbors, something like this:

#!/usr/bin/env ts-node
'use strict';

const goFrom_131072_to_1024 = (v: number[]) => {

  let ret = [...v].sort();

  const reduceByHalf = (v: any[]) => {
    return v.reduce((a,b,currentIndex) => {
      
      if(currentIndex % 2 !== 0){
         return [a[0],b]
      }
      
      a[0].push((a[1]   b)/2); // take average of 2 neighbors
      return [a[0], null];

    },[[], null]);
  };

  while(ret.length > 1024){
    console.log(ret.length);
    ret = reduceByHalf(v)[0];
  }

  return ret;
}

console.log(
  goFrom_131072_to_1024(
    new Array(131072).fill(null).map((v,i) => i)
  )
);

when I run it (with ts-node), gets stuck at 65536, not really sure why. There is also one potential bug where if the list had a length that's an odd number, the last element would get lost (but it's an even numbered length so fine for now). Is there a more elegant way to do this?

(Ultimately the reason I am doing this is that the numbers in the list represent a histogram (probability distribution) and I want to represent the population with a smaller sample. Combining (in this case, averaging) neighbors might be a relatively crude way to do this, will take advice on better ways.)

CodePudding user response：

I'm not sure what you would call "elegant". Why not use a bigger average group? If you want to reduce 131072 by a factor of 128, then you could just make average of 128 numbers.

For example, if you do:

[1, 2, 3, 4, 5, 6, 7, 8]

And you want to reduce the list of 8 elements to 2 elements, you would make average groups of 4.

[[1, 2, 3, 4], [5, 6, 7, 8]]

Which would be:

[ (1 2 3 4)/4 ], [ (5 6 7 8)/4 ]

Which would get you the same result:

[ 2.5, 6.5 ]

So now, all you need to do is groups of 2^n and get the average of those groups.

function groupBy(list, t){
    let grouped = [];
    let max = Math.ceil(list.length/t);
    for(let i = 0; i < max; i  ){
        grouped.push(list.slice(i*t, (i 1)*t));
    }
    return grouped;
}

function average(list){
   return list.reduce((a, b) => a   b)/list.length;
}

function reduceByFactorOfN(list, factor){
   return groupBy(list, 2**factor).map(average);
}