使用 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
,并且每个变量对应 list
、i
和组的元素组合,j
:
- xij:如果
list
的元素 i
分配给组 j
,则等于 1
,否则等于0
.
我们得到以下系数。
ci:list
的元素 i
的成本 (list[i][:size]
)
pi:list
的元素 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,11
和 10,10,2
。
不同的做法:
这是我对贪心算法的看法:
- 按降序排列项目。
- 得到
subset limit
= total input size
/ no of subsets
- forEach 子集
-
- 从输入中选择项目,这将使我们接近
subset limit
。
- 将剩余的项目放在最后一个子集中。或者平均分配。
// 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>
请注意,可以通过多种方式改进代码。例如。在排序的时候,我们可以把重复项放在第一位,这样避免重复比使总和更接近更优先。
需要用更多的测试用例进行测试。
问题- 下面的算法遍历对象数组并将对象分配给三个子集,使得每个子集的总和非常接近(贪心算法)。如果您 运行 代码,您会注意到在第一个子集中 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
,并且每个变量对应 list
、i
和组的元素组合,j
:
- xij:如果
list
的元素i
分配给组j
,则等于1
,否则等于0
.
我们得到以下系数。
ci:
list
的元素i
的成本 (list[i][:size]
)pi:
list
的元素i
的 p 值 (list[i][:p]
)S :由
的两个或多个元素共享的一组唯一值list
.list[i][:p]
U(s):
中的每个 slist
的元素集 i,其中list[i][:p] == 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,11
和 10,10,2
。
不同的做法:
这是我对贪心算法的看法:
- 按降序排列项目。
- 得到
subset limit
=total input size
/no of subsets
- forEach 子集
-
- 从输入中选择项目,这将使我们接近
subset limit
。
- 从输入中选择项目,这将使我们接近
- 将剩余的项目放在最后一个子集中。或者平均分配。
// 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>
请注意,可以通过多种方式改进代码。例如。在排序的时候,我们可以把重复项放在第一位,这样避免重复比使总和更接近更优先。
需要用更多的测试用例进行测试。