How to split an array into three arrays in a way they are divided as fairly as possible JavaScript-CodePudding

Here is my array:

const sorted = [
  { pwr: 10 },
  { pwr: 9 },
  { pwr: 9 },
  { pwr: 8 },
  { pwr: 6 },
  { pwr: 6 },
  { pwr: 2 },
  { pwr: 2 },
  { pwr: 1 },
];

What I want to do is dividing it to three separate arrays in a way the total value of pwr in each array be the closest value to the others arrays.

For example this is not fair division at all:

arr1: [ { pwr: 10 },
      { pwr: 9 },
      { pwr: 9 }]

arr2: [ { pwr: 8 },
      { pwr: 6 },
      { pwr: 6 }]

arr3: [ { pwr: 2 },
      { pwr: 2 },
      { pwr: 1 }]

Since the total value of arr1 is 10 9 9 = 28, while the arr2 is 20 and arr3 is just 5 !

The splitted array should be something like this:

arr1: [ { pwr: 10 },
      { pwr: 6 },
      { pwr: 1 }]

arr2: [ { pwr: 9 },
      { pwr: 6 },
      { pwr: 1 }]

arr3: [ { pwr: 9 },
      { pwr: 8 },
      { pwr: 2 }]



arr1 =17
arr2=16
arr3=19
which is somehow fair.

My suggestion is that picking from the first array (which is sorted by default) like this:

In the first stage, arr1 gets first element (index0) and arr2 gets second elemtns (index1), and arr3 gets 2 element (index 2 and index3):

arr1[{pwr: 10}]
arr2[{pwr: 9}]
arr3[{pwr:8},{pwr:6}]

Then, from now on each array gets just one element until the sorted element finishes. I mean we get back to arr1 and give it the next item (index4) then arr2 gets (index5) arr3 (index6) again arr1 (index7) and...

Do you guys have any idea to achieve the most fair arrays? Could you guys provide me with snippets?

CodePudding user response：

I have taken a look at the problem and came up with the following solution. I think it can be done way better but I think it works. The code down below chunks the sorted array into chunks of the size 3 if possible. Then it finds the array with the lowest sum and adds the object with the biggest pwr value to it. That goes until there are not entries in sorted left. The final arrays are in the arrays object and not standalone.

let sorted = [
  { pwr: 10 },
  { pwr: 9 },
  { pwr: 9 },
  { pwr: 8 },
  { pwr: 6 },
  { pwr: 6 },
  { pwr: 2 },
  { pwr: 2 },
  { pwr: 1 },
  { pwr: 1} // <- this was added to test if it works if no even chunks are possible
];

const getSum = (a) => {
  return a.reduce((acc, value) => {
    if (!value) return acc   0;
    return acc   value.pwr;
  }, 0);
}

const chunk = (array, size = 1) => {
  let chunks = [];
  let chunk = [];
  for (let i = 0; i < array.length; i  ) {
    chunk.push(array[i]);
    if ((i   1)  % size === 0) {
      chunks.push(chunk);
      chunk = [];
    };
  };
  if (chunk.length !== 0) {
    chunks.push(chunk);
  };
  return chunks;
};

let arrays = {
  arr1: [],
  arr2: [],
  arr3: []
}

sorted = chunk(sorted, 3);

sorted.forEach((chunk) => {
  let a = [];
  Object.keys(arrays).forEach((arr) => {
    a.push({ name: arr, value: getSum(arrays[arr]) });
  });
  a.sort((a, b) => {
    return a.value - b.value;
  });
  for (let i = 0; i < a.length; i  ) {
    if (chunk[i]) {
      arrays[a[i].name].push(chunk[i]);
    }
  };
});

// this just outputs the result
console.log(arrays);
Object.keys(arrays).forEach((key) => {
  console.log(getSum(arrays[key]));
});

.as-console-wrapper { min-height: 100%!important; top: 0; }