Evenly distribute 2 different values inside an array with JavaScript

user_11792214 0
Viewed 588

I have an array of 2 different values and they need to be distributed evenly.

For example:

array = [1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

and the result I want is:

array = [1, 2, 1, 2, 1, 2, 1, 2, 1, 2]

But also if the ratio is not 1:1 it should be distributed as evenly as possible:

array = [1, 1, 1, 1, 1, 1, 1, 2, 2, 2]
result = [1, 1, 2, 1, 1, 2, 1, 1, 1, 2]

or

array = [1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
result = [1, 1, 1, 1, 1, 2, 1, 1, 1, 1]

What would be the best way to get this working?

I have tried the following, but it only works for my first example:

evenDistribute(array1, array2) {
            const longest = array1.length > array2.length ? array1 : array2;
            const shortest = array1.length > array2.length ? array2 : array1;
            const ratio = Math.floor(longest.length / shortest.length);
            const results = [];

            for (let i = 0; i < shortest.length; i++) {
                for (let j = 0; j < ratio; j++) {
                    results.push(longest[i * ratio + j]);
                }
                results.push(shortest[i]);
            }

            // Grab any that are left over
            for (let i = longest.length - (longest.length % shortest.length); i < longest.length; i++) {
                results.push(longest[i]);
            }
            return results;
        }
arrays javascript
3 Answers

Let's see if this helps

A = '.'
B = '@'

countA = 7
countB = 3


total = countA + countB
groupSize = Math.floor(total / countB)
numGroups = Math.floor(total / groupSize)
halfSize = (groupSize - 1) >> 1
group = A.repeat(halfSize) + B + A.repeat(halfSize)
result = group.repeat(numGroups) + A.repeat(total - group.length * numGroups)
console.log(result)

user_9891210

How about something like this recursive version?

// xs has the smaller length
const _evenDist = (xs, ys, count = Math .round (ys.length / (xs.length + 1))) => 
  xs .length == 0
    ? [... ys]
    : [... ys .slice (0, count), xs[0], ..._evenDist (xs .slice (1), ys .slice (count))] 

const evenDist = (xs, ys) =>
  xs .length > ys.length ? _evenDist(ys, xs) : _evenDist(xs, ys)

console .log (evenDist ([1, 1, 1, 1, 1], [2, 2, 2, 2]) .join (' '))
console .log (evenDist ([1, 1, 1, 1, 1, 1, 1], [2, 2, 2]) .join (' '))
console .log (evenDist ([1, 1, 1, 1, 1, 1, 1, 1, 1], [2]) .join (' '))

const letters = 'abcdefghijklmnopqrstuvwxyz' .split ('')
const digits = '0123456789' .split ('')
console .log (evenDist (letters, digits) .join (' '))
.as-console-wrapper {max-height: 100% !important; top: 0}

Assuming the 2's are in the larger list, we count how many 2's should appear before the first 1, return an array with that many 2, followed by a 1, followed by a recursive call with that many fewer 2's and one fewer 1. The recursion bottoms out when there are no more 1s, and we return the remaining 2s.

We calculate the number of initial 2s by thinking of the holes left with only the 1s in them. Since there are fewer 1s there will be one hole before the first, one hole after the last, and one hole between every two consecutive 1s. That makes n + 1 holes, where n is the number of 1s. Then we divide the number of 2s by this value, and round it to the nearest integer. We could equally well use Math.ceil or Math.floor instead of Math.round. Those would put all the longer runs of 2s to one end or the other. round distributes them more evenly, and seems slightly better to me.

Note that this technique knows nothing about the contents of the two arrays, and in the example you can see it interspersing the letters and the digits into a single array.

Addendum

The answer from Ben Stephens prompted me to think about how this could be extended to handle the dispersal of multiple different sets, not just two. I found two approaches I like.

The first one is incomplete, and I probably won't bother to complete it, because the other one below seems good enough and is more in keeping with the answer above. It is based on the Huntington-Hill method used to apportion the seats in the US House of Representatives. Although used elsewhere, mostly what it does is to divide the 435 House seats among the 50 states. But it has the nice property that "If the number of seats was equal in size to the number of votes cast, this method would guarantee that the apportionments would equal the vote shares of each party." I adapted an implementation of this method I wrote some time ago, tracking the positions of the next selections alongside their count. (There was an ugly workaround where I started with a dummy element in each set to match the US apportionment requirement that every state get at least one vote. Those were removed at the end.) It's not complete, but it seems as though it would work. You can see my progress if you like, but I won't include it here.

The other version uses the above and adds a disperse function which takes an array of arrays and separates out the longest one, recursively calling itself on the remaining ones and then calling evenDist on that long one and those results. And of course the recursion bottoms out when there are two or fewer arrays left. I don't know if there's any notion of a perfect result for this problem, but these seem fairly good.

// xs has the smaller length
const _evenDist = (xs, ys, count = Math .round (ys.length / (xs.length + 1))) => 
  xs .length == 0
    ? [... ys]
    : [... ys .slice (0, count), xs[0], ..._evenDist (xs .slice (1), ys .slice (count))] 

const evenDist = (xs, ys) =>
  xs .length > ys.length ? _evenDist(ys, xs) : _evenDist(xs, ys)

const findLongest = (
  xss, 
  max = Math .max (... xss .map (xs => xs .length)), 
  i = xss .findIndex (x => x .length == max)
) =>
  [xss [i], [... xss .slice (0, i), ... xss .slice (i + 1)]]

const disperse = (xss) =>
  xss .length < 2
    ? [... (xss [0] || [])]
    : (([ys, yss]) => evenDist (ys, disperse (yss))) (findLongest (xss))

console .log (disperse (['aaaaaaaa', 'bbb', 'cc']).join(' '))
console .log (disperse (['aaaaaaaa', '-----']).join(' '))
console .log (disperse (['@@@@@@@@', '-----', 'oooooo']).join(' '))
console .log (disperse (['@'.repeat(26), '.'.repeat(10), 'o'.repeat(14)]) .join (' '))
console .log (disperse (['@'.repeat(26), '-'.repeat(24)]) .join (' '))
const letters = 'abcdefghijklmnopqrstuvwxyz'
const digits = '0123456789'
const dashes = '--------------'
const dots = '....'
console .log (disperse ([digits, dashes]) .join (' '))
console .log (disperse ([letters, digits, dashes]) .join (' '))
console .log (disperse ([letters, digits, dashes, dots]) .join (' '))
.as-console-wrapper {max-height: 100% !important; top: 0}

user_12436410

This doesn't quite do what you want, and has the downside of treating '2' and 2 in the same way (due to using object keys as part of the process) but I was wondering if it might be useful in some way:

const disperse = (start) => {
  const counts = start.reduce((acc, value) => Object.assign(acc, { [value + '']: (acc[value + ''] || 0) + 1}), {});

  const weights = Object.fromEntries(
    Object.entries(counts).map(([value, count]) => ([value, 1 / count]))
  );

  let usage_val = Object.fromEntries(
    Object.entries(counts).map(([value, count]) => ([value, 0]))
  );

  let usage = { ...usage_val };

  const compare_weight = (key) => usage_val[key] + (weights[key] / 2);

  let result = [];

  for(let i = 0, next = null; i < start.length; i++) {
    Object.keys(counts).reverse().forEach((key) => {
      if(usage[key] === counts[key])
        return;
      if(next === null || compare_weight(key) <= compare_weight(next))
        next = key;      
    });

    result.push(next);
    usage[next] += 1;
    usage_val[next] += weights[next];
  }
  
  return result;
};


console.log(disperse([1, 1, 1, 1, 1, 1, 1, 2, 2, 2]).join(' '));
console.log(disperse([1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3]).join(' '));
console.log(disperse([1, 1, 1, 1, 1, 2, 2, 2, 2, 2]).join(' '));
.as-console-wrapper {max-height: 100% !important; top: 0}

user_144549390
Related