使用 JavaScript 在子集数组之间交换重复值

Exchanging Duplicate Values Between Subset Arrays with JavaScript

问题- 下面的算法遍历对象数组并将对象分配给三个子集,使得每个子集的总和非常接近(贪心算法)。如果您 运行 代码,您会注意到在第一个子集中 p:11 出现两次,在第三个子集中 p:10 出现两次。我不想让 p 值多次出现在同一个数组中。
问题 - 我如何确保算法中 p 的值不会多次出现在同一个子集数组中,因为对象被分配到子集数组,同时确保每个子集数组的和还是一样?

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)

这可以作为一个整数线性优化问题求解,具有一个连续变量 t,并且每个变量对应 listi 和组的元素组合,j:

  • xij:如果 list 的元素 i 分配给组 j,则等于 1,否则等于0.

我们得到以下系数。

  • cilist 的元素 i 的成本 (list[i][:size])

  • pilist 的元素 i 的 p 值 (list[i][:p])

  • S :由 list.

    的两个或多个元素共享的一组唯一值 list[i][:p]
  • U(s):list 的元素集 i,其中 list[i][:p] == s,对于 S

    中的每个 s

公式如下

(1) 分钟 t

受制于:

(2) t >= ∑i xijcij 对于每个 j

(3) ∑j xij = 1 对于每个 i

(4) ∑U(s) xij <= 1 对于 S

中的每个 j 和 s

(5) xij 对于所有 i,j 对

等于 0 或 1
  • (1) 和 (2) 寻找 minimax 解决方案,使最大组成本最小化,这往往会降低总成本并使各组的成本均等。
  • (3) 要求 list 的每个元素恰好分配给一个组
  • (4) 确保 list 中没有两个具有相同 list[:p] 值的元素被分配到同一组。

答案:

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

您不能在所有情况下都保持相同的总和。考虑代码的输出:

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}, ]

在这里,我们可以将 {p:11 size:25}{p:8 size:25} 交换,总和保持不变。
但是在 {p:10 size:75} 的情况下,没有其他大小为 75 的项目。最接近的情况是用 {p:4 size:50} 交换它。现在总和变成 317,317,275 不一样了。


最好的解决方案是找到所有组合,不重复,然后选择总和最接近的组合。

错误:
你的算法有一个错误。考虑一个没有重复的输入:

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

您的代码产生以下子集:

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

理想的总数应该是 22,22,分组应该是 11,1110,10,2



不同的做法:
这是我对贪心算法的看法:

  1. 按降序排列项目。
  2. 得到 subset limit = total input size / no of subsets
  3. forEach 子集
    • 从输入中选择项目,这将使我们接近 subset limit
  4. 将剩余的项目放在最后一个子集中。或者平均分配。

// 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>

请注意,可以通过多种方式改进代码。例如。在排序的时候,我们可以把重复项放在第一位,这样避免重复比使总和更接近更优先。
需要用更多的测试用例进行测试。