Question

0

350

Views

Exchanging Duplicate Values Between Subset Arrays with JavaScript

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)

over 4 years ago · Santiago Trujillo

1 answers

Answer question

0

Answer question

Find remote jobs

Answer 1 · 2022-03-25T13:52:34.976Z

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:

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

We are given the following coefficients.

c_i: cost of element i of list (list[i][:size])
p_i: 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 x_ijc_ij for each j

(3) ∑_j x_ij = 1 for each i

(4) ∑_U(s) x_ij <= 1 for each j and s in S

(5) x_ij 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.

0

350

Exchanging Duplicate Values Between Subset Arrays with JavaScript

1 answers

0

Find remote jobs

Andres GPT