Tag Archives: Math

Sorting Arrays in JavaScript, from the Inside-Out.

Every now and then I come across questions on StackOverflow that require me to do a bit of thought-work. This particular question was asking to to take an array, such as [‘a’,’b’,’c’,’d’,’e’], and flip it inside out, so that it becomes [‘c’,’d’,’b’,’e’,’a’]. I’m not a particularly mathematical person, so when I discover a difficult to discern pattern, I get excited – such was the case with the code below.

// Arrays to sort
var data = ["a","b","c","d","e"],
    info = ["a","b","c","d"];

// Sort array from inside-out ['a','b','c','d','e'] 
// Resulting in the following ['c','d','b','e','a']
function gut (arr) {
    
    // Resulting array, Counting variable, Number of items, 
    // initial Location
    var out = [], cnt, 
        num = arr.length, 
        loc = Math.floor(num/2);
    
    // Cycle through as many times as the array is long
    for (cnt = 0; cnt < num; cnt++)
        // Protecting our cnt variable
        (function () {
            // If our array has an odd number of entries
            if (num % 2) {
                // If on an odd iteration
                if (cnt % 2) {
                    // Move location forward
                    loc = loc + (+cnt); 
                } else {
                    // Move location backwards
                    loc = loc + (-cnt);  
                }
            // Our array has an even number of entries
            } else {
                // If on an odd iteration
                if (cnt % 2) {
                    // Move location backwards
                    loc = loc + (-cnt);
                } else {
                    // Move location forwards
                    loc = loc + (+cnt);
                }
            }
            // Push val at location to new array
            out.push(arr[loc]);
        })()
            
    // Return new array
    return out;
    
}

// Test with two arrays; even and odd sizes.
console.log(gut(data), gut(info));‚Äč

Which results in the following output:

["c", "d", "b", "e", "a"]
["c", "b", "d", "a"]

Perhaps you will find some use for it.

n Parts for Sum in PHP

I was bouncing around on Stack Overflow, answering questions here, voting on questions and answers there, when I came across a question on how to construct an array of arbitrary size, whose members add up to an explicit sum. This sounded fun, especially since math has always been an area I’d like to see some personal growth in.

So I set out to answer the question, jotting down some pseudo-code in notepad, and working through some functional portions on writecodeonline.com/php and coderpad.org. After about 10 minutes or so I felt as though I had a good solution for the OP (original poster), so I clicked back over to my Stack Overflow tab. To my terror, the question had been closed as a duplicate.

Now what? Did I just waste all that time and brain-power constructing a solution that I cannot even share? Meh, screw it, I’ll share it on my blog!

My first step was to build up an array of values that were each a fraction of the sum, rounded down to keep away from decimals. This would, of course, leave me with a slightly larger number in the end if the sum isn’t equally divisible by the expected number of parts. That’s okay, I’ll just push that last number onto the end of the array.

$sum = 200; 
$parts = 10; 
$valus = array();

for ( $i = 0; $i < $parts; $i++ ) {
  $num = $i < ( $parts - 1 )
    ? floor( $sum / $parts )
    : $sum - array_sum( $valus );
  array_push( $valus, $num );
}

Awesome. This results in an array of values that are almost entirely the same number, with the exception of the last index, which will be slightly larger when the sum doesn’t divide equally.

Next I need to randomize the values. I figured I would cycle back through and have some of the values share the wealth, so to speak. Each number would have a random portion of itself donated to a random sibling. At the very least, any particular number could be reduced to 1, but no lower (more on that in a bit).

foreach ( $valus as $key => &$value ) {
  if ( $value == 1 ) continue;
  $rVal = rand( 1, $value - 1 );
  $rKey = rand( 1, $parts );
  while ( $rKey == ( $key + 1 ) )
    $rKey = rand( 1, $parts );
  $value -= $rVal;
  $valus[--$rKey] += $rVal;
}

That’s it! (KEEP READING! One important change yet to be made) Tell it how much, and how many, and it builds an array of randomized values for you. One run of the code against the above settings resulted in the following output:

Array
(
  [0] => 26
  [1] => 59
  [2] => 4
  [3] => 61
  [4] => 35
  [5] => 1
  [6] => 2
  [7] => 7
  [8] => 1
  [9] => 4
)

One interesting thing I noticed after toying with the input was that if your sum is less than your number of parts, the code will at times provide a negative number in order to provide adjusted values for each key. For example:

$sum = 2;
$parts = 5;

Produced the following results after one run:

Array
(
  [0] => -1
  [1] => 0
  [2] => -1
  [3] => 3
  [4] => 1
)

Count it up, -1 + 0 + -1 + 3 + 1 indeed equals 2. Of course this wasn’t at all what I wanted. But it did cause me to consider what would happen if somebody wanted more parts than their provided sum. This lead me to return to my share the wealth portion and rewrite the first condition:

if ( $value <= 1 ) continue; // change == to <=

Now, whenever our current value is less than or equal to 1, we skip it. It is possible for the value to be zero already, because we floor the results of the division in earlier code. If the sum is less than our parts, that result will be a fraction, which we promptly round down to 0. This will now prevent the code from further reducing the value from 0 into negative numbers. In cases where our sum is much larger than our parts, we don’t want to borrow so much from one key that we leave another with 0. This is why I skip if the value is already 1 as well.

So asking again for the following:

$sum = 2;
$parts = 5;

Will output the following array (or one similar to it):

Array
(
  [0] => 0
  [1] => 0
  [2] => 1
  [3] => 0
  [4] => 1
)