1D -> 2D Array W/Normal Curve Sub-Array Lengths

I am trying to break a 1D array into a 2D array where the sub-arrays are of varying lengths. This variance should follow the gaussian curve [or a mound shape]. So, say the 2D array

Solution 1:

I gave it a quick shot and it seems to work. Some potential improvements:

• Input checking for the functions
• It places any possible leftover values into the middle bin. For even-numbered total bins it would benefit from some balancing. After that, it might be good to attempt to sort each bin based on the original index in the input data, since right now things can end up out of order. But if this is just to have non-linearly distributed jobs for a progress bar, the order may not matter.

function probability(s, m, x) {
	var eExp = -Math.pow(x - m, 2) /
		(2 * Math.pow(s, 2));
	return 1/(Math.sqrt(2*Math.PI) * s) *
		Math.pow(Math.E, eExp);
}

function gassianArray(input, nBins) {
	// first try to determine a reasonable value of s so that the outer bins have a value
	var s = 0.1;
	var sMax = 10;
	var m = (nBins - 1) / 2.0;
	var outerBinMinimum = 1 / input.length;
	var p = 0;
	while (true && s <= sMax) {
		p = probability(s, m, 0);
		if (p >= outerBinMinimum) {
			break;
		} else {
			s += 0.1;
		}
	}

	// holds arrays
	var output = [];
	// holds desired array sizes
	var outputLengths = [];
	// fill these based on probability density
	for (var b=0; b<nBins; b++) {
		var n = Math.floor(probability(s, m, b) * input.length);
		output.push([]);
		outputLengths.push(n);
	}

	// fill arrays from outside, leaving extra values for the middle
	var midIndex = Math.floor(m);
	// left side
	for (var i=0; i<midIndex; i++) {
		for (var j=0; j<outputLengths[i]; j++) {
			output[i].push(input.shift());
		}
	}
	// right side
	for (var i=nBins-1; i>=midIndex; i--) {
		for (var j=0; j<outputLengths[i]; j++) {
			output[i].push(input.pop());
		}
		output[i].reverse();
	}
	// whatever remains goes in the "middle"
	while (input.length !== 0) {
		output[midIndex].unshift(input.pop());
	}

	return output;
}

var input = ["A","B","C","D","E","F","G","H","I","J","K"];
var n = 5;
console.log(gassianArray(input, n));
/*
[ [ 'A' ],
  [ 'B', 'C' ],
  [ 'E', 'D', 'F', 'G', 'H' ],
  [ 'I', 'J' ],
  [ 'K' ] ]
*/


var input = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"];
var n = 6;
console.log(gassianArray(input, n));
/*
[ [ 'A' ],
  [ 'B', 'C', 'D', 'E' ],
  [ 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N' ],
  [ 'O', 'P', 'Q', 'R', 'S', 'T', 'U' ],
  [ 'V', 'W', 'X', 'Y' ],
  [ 'Z' ] ]
*/

Solution 2:

Very interesting challenge. :)

I have played a bit and here is what I came up with:

function chunk(arr, start, n) {
  if (arr.length < n) {
    return null;
  }

  return arr.splice(start, n);
}

function gaussianArray(arr, max) {
  const len = arr.length;

  if (max > len) {
    return [arr];
  }

  const curve = [];

  // Extract middle.
  const mid = Math.floor(len / 2);
  const startIndex = mid - (max / 2) + 1;
  const highest = arr.splice(startIndex, max);

  curve.push(highest);

  // Splits the rest in 2 arrays; left side and right side, middle already excluded.
  const leftArr = arr.slice(0, startIndex);
  const rightArr = arr.slice(startIndex, len);

  let leftMax = max;
  let rightMax = max;

  // Adds chunks from left side.
  while (leftArr.length) {
    const leftChunk = chunk(leftArr, leftArr.length - leftMax, leftMax);

    if (leftChunk) {
      curve.unshift(leftChunk);
    } else {
      leftMax--;
    }
  }

  // Adds chunks from right side.
  while (rightArr.length) {
    const rightChunk = chunk(rightArr, 0, rightMax);

    if (rightChunk) {
      curve.push(rightChunk);
    } else {
      rightMax--;
    }
  }

  return curve;
}

console.log(JSON.stringify(gaussianArray(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 1)));
console.log(JSON.stringify(gaussianArray(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 2)));
console.log(JSON.stringify(gaussianArray(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 4)));
console.log(JSON.stringify(gaussianArray(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 8)));
console.log(JSON.stringify(gaussianArray(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 16)));

It is not exactly what you want, but I think it should be close to solve your progress bar problem...

Solution 3:

This was more inline with what I was thinking. I greatly dislike the way I am finding sigma. I know I should just reorder the formula to calculate it, but I have yet to get that to work. Anyway, here is the, "answer" though it fails for the smaller arrays I provided as examples in the question, it successfully does what I needed to do. If anyone has improvements they'd like to add, just let me know.

var gaussianRefactor = function(srcOneDimentionalArray, srcMaxArrayLength) {
  var finalArray = [];
  if (srcOneDimentionalArray.length <= srcMaxArrayLength) {
    finalArray.push(srcOneDimentionalArray);
    return finalArray;
  }
  if (srcMaxArrayLength === 1) {
  for(var lengthOne = 0; lengthOne < srcOneDimentionalArray.length; lengthOne++)
    finalArray.push([srcOneDimentionalArray[lengthOne]]);
    return finalArray;
  }
  var maxArrayLength = srcMaxArrayLength;
  var oneDimentionalArray = srcOneDimentionalArray.slice(0);
  for (var x = srcMaxArrayLength; x > 1 && maxArrayLength / oneDimentionalArray.length > 0.3333; x--) {
    maxArrayLength--;
  }
  var standardChunkSize = srcOneDimentionalArray.length / maxArrayLength;
  var predictedSize = (3 * Math.floor(standardChunkSize)) % 2 === 0 ? 3 * Math.floor(standardChunkSize) + 1 : 3 * Math.floor(standardChunkSize);
  var predictedSizeCenter = Math.ceil(predictedSize / 2);
  var sigma = 0.2034185 * Math.pow(standardChunkSize, 1.963449);
  var multiplicand = 1 / (Math.sqrt(sigma) * Math.sqrt(2 * Math.PI));
  var centerGauss = maxArrayLength / multiplicand;
  var mu = 0;
  var delta;
  var fraction;
  var exponent;
  var full;
  var subArrayLength;
  var subArray;
  var notWideEnough = true;
  var maxElements;
  var maxAttempts = Math.max(Math.ceil(sigma), 100);
  var currentAttempts = 0;
  while (notWideEnough && currentAttempts < maxAttempts) {
    maxElements = 0;
    for (var j = 0; j < predictedSize; j++) {
      delta = (j - predictedSizeCenter) - mu;
      fraction = delta / Math.sqrt(sigma);
      exponent = -0.5 * Math.pow(fraction, 2);
      full = multiplicand * Math.exp(exponent);
      subArrayLength = Math.floor(full * centerGauss);
      maxElements += subArrayLength;
    }
    if (maxElements >= srcOneDimentionalArray.length) {
      notWideEnough = false;
    } else {
      sigma = sigma + sigma * 0.05;
    }
    currentAttempts++;
  }
  if (currentAttempts === maxAttempts) {
    return false;
  }

  for (var i = 0; i < predictedSize; i++) {
    delta = (i - predictedSizeCenter) - mu;
    fraction = delta / Math.sqrt(sigma);
    exponent = -0.5 * Math.pow(fraction, 2);
    full = multiplicand * Math.exp(exponent);
    subArrayLength = Math.floor(full * centerGauss);
    if (subArrayLength < 1 || oneDimentionalArray.length < 1) {
      continue;
    }
    subArray = oneDimentionalArray.slice(0, subArrayLength);
    oneDimentionalArray = oneDimentionalArray.slice(subArrayLength, oneDimentionalArray.length);
    finalArray.push(subArray);
  }
  return finalArray;
}

INPUT

gaussianRefactor(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 1)
gaussianRefactor(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 2)
gaussianRefactor(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 4)
gaussianRefactor(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 8)
gaussianRefactor(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 16)

OUTPUT

[["A"],["B"],["C"],["D"],["E"],["F"],["G"],["H"],["I"],["J"],["K"]]
[["A"],["B"],["C"],["D"],["E"],["F","G"],["H"],["I"],["J"],["K"]]
[["A"],["B"],["C","D"],["E","F","G"],["H","I"],["J"],["K"]]
[["A"],["B"],["C","D"],["E","F","G"],["H","I"],["J"],["K"]]
[["A","B","C","D","E","F","G","H","I","J","K"]]

-- EDIT 2021 -- https://jsfiddle.net/brightmatter_og/xzfwjeaq/ I found the answer I was seeking. I will put it here if anyone is interested.

function removeMeFromTheList(removeMe, theList) {
  for (let i = 0; i < theList.length; i++) {
    if (theList[i] === removeMe) {
      theList.splice(i, 1);
      return;
    }
  }
}

function makeListOfGaussianLists(chunkWeights, objects) {
  const listOfLists = [];
  const chunkWeightsSize = Object.keys(chunkWeights).length;
  if (chunkWeightsSize < 1 || objects.length < chunkWeightsSize) {
    console.info("chunkWeights.length:" + chunkWeightsSize + " - objects.length:" + objects.length);
    return null;
  }
  const elementCount = objects.length / chunkWeightsSize;
  let modifiedElementCount = null;
  for (let i = 0; i < chunkWeightsSize; i++) {
    modifiedElementCount = parseInt(chunkWeights[i] * elementCount);
    let innerList = [];
    for (let j = modifiedElementCount; j > 0; j--) {
      const obj = objects[0];
      if (obj == null) {
        break;
      }
      innerList.push(obj);
      removeMeFromTheList(obj, objects);
    }
    listOfLists.push(innerList);
  }
  if (objects.length > 0) {
    do {
      for (let i = 0; i < listOfLists.length; i++) {
        const obj = objects[0];
        if (obj == null) {
          break;
        }
        listOfLists[i].push(obj);
        removeMeFromTheList(obj, objects);
      }
    } while (objects.length > 0);
  }
  return listOfLists;
}

function subListWeightBuilder(partitionCount) {
  const gauss = [];
  const population = 250;
  const chunkWeights = {};
  if (partitionCount > population) {
    return chunkWeights;
  }
  for (let i = 0; i < population * 2; i++) {
    gauss.push(randomGaussian());
  }
  gauss.sort(function(a, b){return a - b});
  const partitionWidth = gauss.length / partitionCount;
  let currentCount = 0;
  let chunkWeightsIndex = 0;
  let pastTheFirst = false;
  for (let j = 0; j < gauss.length; j++) {
    if (currentCount < partitionWidth) {
      chunkWeights[chunkWeightsIndex] = 1 / (Math.abs(gauss[j]) + 0.66);
    } else {
      chunkWeightsIndex++;
      currentCount = 0;
    }
    currentCount++;
  }
  let offset = 0;
  for (let key in chunkWeights) {
    offset += chunkWeights[key];
  }
  offset /= partitionCount;
  offset = (1 - offset) + Number.MIN_VALUE;
  for (let key in chunkWeights) {
    let value = chunkWeights[key];
    chunkWeights[key] = value + offset;
  }
  return chunkWeights;
}

function randomGaussian() {
  let r = 0;
  const iteration = 6;
  for (let i = iteration; i > 0; i--) {
    r += Math.random();
  }
  return r / iteration - 0.5;
}

function pressButton() {
  let partitionCount = 23;
  console.info(makeListOfGaussianLists(subListWeightBuilder(partitionCount), makeRandomString(333).split("")));
  partitionCount = 41;
  console.info(makeListOfGaussianLists(subListWeightBuilder(partitionCount), makeRandomString(666).split("")));
  partitionCount = 67;
  console.info(makeListOfGaussianLists(subListWeightBuilder(partitionCount), makeRandomString(1000).split("")));
  partitionCount = 41;
  console.info(makeListOfGaussianLists(subListWeightBuilder(partitionCount), makeRandomString(1333).split("")));
  partitionCount = 23;
  console.info(makeListOfGaussianLists(subListWeightBuilder(partitionCount), makeRandomString(1666).split("")));
}

function makeRandomString(size) {
  const loops = parseInt(size / 11);
  let theResult = "";
  for(let i = loops; i > 0; i--) {
    theResult += Array(11 + 1).join((Math.random().toString(36) + '00000000000000000').slice(2, 18)).slice(0, 11);
  }
  return theResult += Array((size - 11 * loops) + 1).join((Math.random().toString(36) + '00000000000000000').slice(2, 18)).slice(0, (size - 11 * loops))
}