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.

functionprobability(s, m, x) {
	var eExp = -Math.pow(x - m, 2) /
		(2 * Math.pow(s, 2));
	return1/(Math.sqrt(2*Math.PI) * s) *
		Math.pow(Math.E, eExp);
}

functiongassianArray(input, nBins) {
	// first try to determine a reasonable value of s so that the outer bins have a valuevar 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 arraysvar output = [];
	// holds desired array sizesvar outputLengths = [];
	// fill these based on probability densityfor (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 middlevar midIndex = Math.floor(m);
	// left sidefor (var i=0; i<midIndex; i++) {
		for (var j=0; j<outputLengths[i]; j++) {
			output[i].push(input.shift());
		}
	}
	// right sidefor (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:

functionchunk(arr, start, n) {
  if (arr.length < n) {
    returnnull;
  }

  return arr.splice(start, n);
}

functiongaussianArray(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.

vargaussianRefactor= function(srcOneDimentionalArray, srcMaxArrayLength) {
  varfinalArray= [];
  if (srcOneDimentionalArray.length <= srcMaxArrayLength) {
    finalArray.push(srcOneDimentionalArray);
    return finalArray;
  }
  if (srcMaxArrayLength === 1) {
  for(varlengthOne=0; lengthOne < srcOneDimentionalArray.length; lengthOne++)
    finalArray.push([srcOneDimentionalArray[lengthOne]]);
    return finalArray;
  }
  varmaxArrayLength= srcMaxArrayLength;
  varoneDimentionalArray= srcOneDimentionalArray.slice(0);
  for (varx= srcMaxArrayLength; x > 1 && maxArrayLength / oneDimentionalArray.length > 0.3333; x--) {
    maxArrayLength--;
  }
  varstandardChunkSize= srcOneDimentionalArray.length / maxArrayLength;
  varpredictedSize= (3 * Math.floor(standardChunkSize)) % 2 === 0 ? 3 * Math.floor(standardChunkSize) + 1 : 3 * Math.floor(standardChunkSize);
  varpredictedSizeCenter= Math.ceil(predictedSize / 2);
  varsigma=0.2034185 * Math.pow(standardChunkSize, 1.963449);
  varmultiplicand=1 / (Math.sqrt(sigma) * Math.sqrt(2 * Math.PI));
  varcenterGauss= maxArrayLength / multiplicand;
  varmu=0;
  var delta;
  var fraction;
  var exponent;
  var full;
  var subArrayLength;
  var subArray;
  varnotWideEnough=true;
  var maxElements;
  varmaxAttempts= Math.max(Math.ceil(sigma), 100);
  varcurrentAttempts=0;
  while (notWideEnough && currentAttempts < maxAttempts) {
    maxElements = 0;
    for (varj=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) {
    returnfalse;
  }

  for (vari=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.

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

functionmakeListOfGaussianLists(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);
    returnnull;
  }
  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;
}

functionsubListWeightBuilder(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;
}

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

functionpressButton() {
  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("")));
}

functionmakeRandomString(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))
}