Exchanging Duplicate Values Between Subset Arrays with JavaScript

user_14549241 0
Viewed 368

PROBLEM - The algorithm below loops through an array of objects and assigns the objects to three subsets such that the sum of each subset is very close(greedy algorithm). If you run the code, you will notice that in the first subset p:11 appears twice and in third subset p:10 appears twice. I don't want to have p value appear in the same array more than once.
QUESTION - How can I make sure in the algorithm that the value of p does not appear in the same subset array more than once as the objects are being distributed to the subset arrays while making sure the sum of each subset array is still the same?

let list = [
  {p:2, size:50},{p:4, size:50},{p:5,size:25},
  {p:6, size:167},{p:6, size:167},{p:7, size:50},
  {p:8, size:25},{p:8, size:50},{p:10, size:75},
  {p:10, size:75},{p:11, size:25},{p:11, size:50},
  {p:12, size:25},{p:13, size:50},{p:14,size:25}
]

function balance_load(power_load_array, number_of_phases) {
 const sorted = power_load_array.sort((a, b) => b.size - a.size); // sort descending

 const output = [...Array(number_of_phases)].map((x) => {
   return {
     sum: 0,
     elements: [],
   };
 });

 for (const item of sorted) {
   const chosen_subset = output.sort((a, b) => a.sum - b.sum)[0];
   chosen_subset.elements.push({p:item.p, size:item.size});
   chosen_subset.sum += item.size;
 }

 return output
}

let p = balance_load(list,3)

console.log(p)

algorithm javascript
2 Answers

This can be solved as an integer linear optimization problem with one continuous variable, t, and one variable for each combination of element of list, i and group, j:

  • xij: equals 1 if element i of list is assigned to group j, else it equals 0.

We are given the following coefficients.

  • ci: cost of element i of list (list[i][:size])

  • pi: value of p for element i of list (list[i][:p])

  • S : set of unique values list[i][:p] that are shared by two or more elements of list.

  • U(s) : set of elements i of list for which list[i][:p] == s, for each s in S

The formulation is as follows.

(1) min t

subject to:

(2) t >= ∑i xijcij for each j

(3) ∑j xij = 1 for each i

(4) ∑U(s) xij <= 1 for each j and s in S

(5) xij equals 0 or 1 for all i,j pairs

  • (1) and (2) seeks seeks a minimax solution that minimizes the maximum group cost, which tends to both reduce total costs and equalize costs over the groups.
  • (3) requires each element of list to be assigned to exactly one group
  • (4) ensures that no two elements of list that have the same value of list[:p] are assigned to the same group.
user_2569700

Answer:

How can I ... while making sure the sum of each subset array is still the same?

You can't keep the sum same in every case. Consider the output from your code:

sum: 317: [{"p":6,"size":167}, {"p":7,"size":50}, {"p":11,"size":50}, {"p":11,"size":25}, {"p":14,"size":25}, ]
sum: 292: [{"p":6,"size":167}, {"p":4,"size":50}, {"p":13,"size":50}, {"p":8,"size":25}, ]
sum: 300: [{"p":10,"size":75}, {"p":10,"size":75}, {"p":2,"size":50}, {"p":8,"size":50}, {"p":5,"size":25}, {"p":12,"size":25}, ]

Here, we can swap {p:11 size:25} with {p:8 size:25} and the sums remain same.
But in case of {p:10 size:75}, there is no other item with size 75. Closest case would be to swap it with {p:4 size:50}. Now sums become 317,317,275 which are not same.


Best solution would be to find all combinations, without duplicates, and pickup the one with nearest sums.

Bug:
Your algorithm has a bug. Consider an input, without duplicates:

Power load array:
 [{"p":1,"size":2},{"p":2,"size":10},{"p":3,"size":10},{"p":4,"size":11},{"p":5,"size":11}]

No of phases: 2

Your code yields following subsets:

sum: 23: [{"p":4,"size":11}, {"p":3,"size":10}, {"p":1,"size":2}, ]
sum: 21: [{"p":5,"size":11}, {"p":2,"size":10}, ]

Ideal sums should be 22,22 and groupings should be 11,11 and 10,10,2.


Different approach:
Here is my flavor of the greedy algorithm:

  1. sort items in descending order.
  2. get the subset limit = total input size / no of subsets
  3. forEach subset
    • pick items from input which will get us close to the subset limit.
  5. put remaining items in last subset. Or distribute evenly.

// DEMO ----------------------------
// 1. no duplicates
let list = [{p: 1, size: 2},
  {p: 2, size: 10}, {p: 3, size: 10},
  {p: 4, size: 11}, {p: 5, size: 11},
]
printInput(list);
printOutput(balance_load(list, 2));


// 2. last two(size:11) are duplicates
list = [{p: 1, size: 2},
  {p: 2, size: 10 }, {p: 3, size: 10},
  {p: 4, size: 11 }, {p: 4, size: 11},
]
printInput(list);
printOutput(balance_load(list, 2));

// 3. original input from the opening post
list = [
  { p: 2, size: 50 }, { p: 4, size: 50 }, { p: 5, size: 25 },
  { p: 6, size: 167 }, { p: 6, size: 167 }, { p: 7, size: 50 },
  { p: 8, size: 25 }, { p: 8, size: 50 }, { p: 10, size: 75 },
  { p: 10, size: 75 }, { p: 11, size: 25 }, { p: 11, size: 50 },
  { p: 12, size: 25 }, { p: 13, size: 50 }, { p: 14, size: 25 }
];
printInput(list);
printOutput(balance_load(list, 3));


// implementation --------------------
function balance_load(power_load_array, number_of_phases) {
  const sortFunction = (a, b) => b.size - a.size;
  const sorted = power_load_array.sort(sortFunction); // sort descending

  const output = [...Array(number_of_phases)].map(_ => ({
    // TODO: can be converted to a proper class
    sum: 0,
    elements: [],

    addItem(item) {
      this.sum += item.size;
      this.elements.push({ ...item });
    },
    addItems(items) {
      items.forEach(e => this.addItem(e));
    },
    contains(item) {
      return this.elements.findIndex(e => e.p === item.p) !== -1;
    },
    toString() {
      let out = `sum: ${this.sum}: <span class='item'>[`;
      this.elements.forEach(e => out += JSON.stringify(e) + ', ');
      out += ']</span>\n';
      return out;
    }
  }));


  let sum = sorted.reduce((a, b) => a + b.size, 0);
  let limit = sum / number_of_phases;
  limit += sorted[sorted.length - 1].size; // average + smallest item

  out.innerHTML += `sum= ${sum}\nsubset limit= ${limit}\n`;

  // fill all subsets one after other
  output.forEach(o => {
    let item = null;

    // first add biggest item
    if (sorted.length > 0) {
      o.addItem(sorted.shift());
    }

    // keep adding to the subset till we reach the average limit
    for (let i = 0; i < sorted.length; i++) {
      item = sorted.shift();
      if ((limit >= o.sum + item.size) && !o.contains(item)) {
        o.addItem(item);
      } else {
        sorted.push(item); // recycle
      }
    }
    sorted.sort(sortFunction);
  });

  // add rest of the stuff to the last subset
  // TODO: add logic to destribute evenly
  output[output.length - 1].addItems(sorted);
  return output
}

function printInput(list) {
  out.innerHTML += `<hr>\nInput: <span class='item'>${JSON.stringify(list)}</span>\n`;
}

function printOutput(list) {
  list.forEach(e => out.innerHTML += e);
}
.item { font-size: .6rem; color: brown; }
<pre id="out"></pre>

Note, the code can be improved in many ways. E.g. While sorting, we can put duplicate items first, so avoiding duplicates will have more priority than bringing sums closer.
Need to test with more test cases.

user_152739680
Related