使用多个函数以最佳方式拆分数组
Split array in the best possible way with multiple functions
我正在寻找一个算法名称，最好是一个可以采用数组并以尽可能最好的方式在函数之间拆分它的库。
我不关心复杂性（它适用于非常低的数据集）。
递归检查就足够了。
一个很好的例子是数组：
const list = [{gender: "female"}, {gender: "female"}, {gender: "female"}, {gender: "male"}]
所以如果我们运行它具有特殊功能
specialFunc(list, [(val) => val === 'female', (val) => val === 'male']);
我们会得到这个
[
[{gender: "female"}, {gender: "female"}, {gender: "female"}],
[{gender: "male"}]
]
因为这是我们可以获得的最佳拆分。
但是，如果我们运行它通过这个函数：
specialFunc(list, [(val) => !!val, (val) => val === 'male']);
我会得到这个：
[
[{gender: "female"}, {gender: "female"}, {gender: "female"}],
[{gender: "male"}]
]
“尽可能最好的方式”是指每个数组之间的（数组长度的）数字距离应该是最小的，并且每个数组中的记录数应该是最大的。
我已经搜索了很多 npmjs 和 github 但找不到任何东西。
非常非常感谢！
function splitGroups<T>(items: T[], filters: ((x: T) => boolean)[]) {
let options = filters.map(f => items.filter(f));
let groups = filters.map((_, index) => ({ data: [] as T[], index }));
let res: T[][] = [];
while (options.reduce((partial_sum, a) => partial_sum + a.length, 0) > 0) {
groups.sort((a, b) => a.data.length - b.data.length);
let smallGroup = groups[0];
const smallGroups = groups.filter(g => g.data.length === smallGroup.data.length);
if (smallGroups.length > 1) {
smallGroup = smallGroups[Math.floor(Math.random() * (smallGroups.length - 1))];
}
if (options[smallGroup.index].length === 0) {
res.push(smallGroup.data);
groups = groups.filter(x => x !== smallGroup);
continue;
}
const item = options[smallGroup.index][0];
options = options.map(x => x.filter(y => y !== item));
smallGroup.data.push(item);
}
res = [...res, ...groups.map(x => x.data)];
return res;
}
function accurateSplitGroups<T>(items: T[], filters: ((x: T) => boolean)[], times: number) {
const options: { data: T[][]; diff: number }[] = [];
for (let i = 0; i < times; i++) {
const res = splitGroups(items, filters);
let diffBetweenGroups = 0;
const groupsLens = res.map(x => x.length);
for (let i = 0; i < groupsLens.length; i++) {
for (let j = 0; j < groupsLens.length; j++) {
diffBetweenGroups += Math.abs(groupsLens[i] - groupsLens[j]);
}
}
options.push({ data: res, diff: diffBetweenGroups });
}
return options.sort((a, b) => a.diff - b.diff)[0].data;
}
const items = [{ gender: 'female' }, { gender: 'female' }, { gender: 'female' }, { gender: 'male' }];
const filters = [(x: any) => !!x.gender, (x: any) => !!x.gender];
const res = accurateSplitGroups(items, filters, 100);
const b = res;
我认为我理解这些要求。您有许多要用于对项目进行分组的谓词函数。对于同一项目，多个谓词可能 return 为真，因此可以使用各种分组。您想要找到一个分组，使结果大小的变化最小化。
我觉得你的例子不是很有说服力。我会尝试我自己的。如果您的项目是 8, 6, 7, 5, 3, 0, 9] 并且您有三个谓词：(n) => n < 7、(n) => n > 3 和 (n) => n % 2 == 1，那么 8 只能进入第二组（它是大于 3，但不小于 7 且不为奇数。）6 可以在前两组中的任何一个中，5 可以在其中任何一个中，依此类推，如下所示：
8 6 7 5 3 0 9
[[1], [0, 1], [1, 2], [0, 1, 2], [0, 2], [0], [1, 2]]
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | | | | | | |
| +--|----|--|----+--|--|----+--|----+----|--|------> Group 0 (n => n < 7)
| | | | | | | | |
+-------+----+--|-------+--|-------|---------+--|------> Group 1 (n => n > 3)
| | | |
+----------+-------+------------+------> Group 2 (n => n % 2 == 1)
由于第一个有一个选择，第二个有两个，第三个有两个，依此类推，可能的分区数是1 * 2 * 2 * 3 * 2 * 1 * 2，或48。它们可能看起来像这样：
[// < 7 > 3 odd
[ [6, 5, 3, 0], [8, 7, 9], [] ],
[ [6, 5, 3, 0], [8, 7], [9] ],
[ [6, 5, 0], [8, 7, 9], [3] ],
[ [6, 5, 0], [8, 7], [3, 9] ],
// ... (42 rows elided)
[ [0], [8, 6, 9], [7, 5, 3] ],
[ [0], [8, 6], [7, 5, 3, 9] ]
]
然后，我们需要从中选择分区大小变化最小的分区。我们可以对这个 1 使用统计方差，即值与其平均值距离的平方和，因此 [[6, 5, 3, 0], [8, 7, 9], []]，长度为 4，3 和 0；这有 8.667 的方差。第二个的长度为 4、2 和 1，方差为 4.667。我们最好的可能性是 3、2 和 2，方差为 0.667。所以像 [[6, 5, 0], [8, 7], [3, 9]] 这样的答案是合理的。可能有很多人有类似的行为；下面的实现只是选择第一个。
如果这正确地描述了问题，那么这里是一些我认为可以处理它的代码：
const range = (lo, hi) => Array .from ({length: hi - lo}, (_, i) => i + lo)
const sum = (ns) => ns .reduce ((a, b) => a + b, 0)
const filterMap = (f, m) => (xs) =>
xs .flatMap ((x, i, a) => f (x, i, a) ? [m (x, i, a)] : [])
const cartesian = ([xs, ...xss]) =>
xs == undefined
? [[]]
: xs .flatMap (x => cartesian (xss) .map (ys => [x, ...ys]))
const variance = (ns, avg = sum (ns) / (ns .length || 1)) =>
sum (ns .map (n => (n - avg) * (n - avg)))
const groupIndices = (count) => (xs) =>
Object .values (xs .reduce (
(a, x, i) => ((a [x] .push (i)), a),
Object .fromEntries (range (0, count) .map (n => [n, []]))
))
const specialFunc = (xs, preds) =>
cartesian (xs .map ((x) => filterMap ((pred, i) => pred (x), (_, i) => i) (preds)))
.map (groupIndices (preds .length))
.reduce (
({min, v}, xs, _, __, v2 = variance (xs .map (x => x .length))) =>
v2 < v ? {min: xs, v: v2} : {min, v},
{min: [], v: Infinity}
) .min .map (ys => ys .map (i => xs [i]))
console .log (specialFunc (
[8, 6, 7, 5, 3, 0, 9],
[n => n < 7, n => n > 3, n => n % 2 == 1]
)) //=> [[6, 5, 0], [8, 7], [3, 9]]
.as-console-wrapper {max-height: 100% !important; top: 0}
我们从一些相当标准的实用函数开始。 range 计算一个整数范围，包括底部，不包括顶部，例如，range (3, 12) returns [3, 4, 5, 6, 7, 8, 9 ,10, 11]. sum只是对一个数字数组求和，filterMap结合了过滤和映射，首先测试一个输入是否匹配一个过滤器，如果是，则在将结果放入结果之前转换结果。这个实现是不寻常的，因为过滤器和映射函数不仅需要值，还需要索引和数组属性，如 map 和 filter。我们需要它，因为我们将使用它来收集匹配的索引。 （还有很多其他方法可以做到这一点，但是 filterMap 是一个有用的、可重复使用的函数。） cartesian returns 笛卡尔积数组的数组。例如，cartesian ([1, 2, 3], [true], ['a', 'b']]) 将 return [[1, true, 'a'], [1, true, 'b'], [2, true, 'a'], [2, true, 'b'], [3, true, 'a'], [3, true, 'b']]。最后 variance 计算数字列表的统计方差。
然后我们有一个辅助函数，groupIndices。这可能最容易用一个例子来展示。我们的笛卡尔积的 48 个结果之一将是 [1, 0, 1, 0, 2, 0, 1]，这意味着我们的原始数字（8, 6, 7, 5, 3, 0, 9]，recall）在 1、0、[=30 组中=]、0、2、0 和 1。 groupIndices 采用组数，然后采用笛卡尔组合，并将其转换为 [[1, 3, 5], [0, 2, 6], [4]]，给出映射到每个组的值的 索引 。 （如果我没时间的话，我相信我们可以跳过这个与索引的工作并直接针对值，但这有效。）
现在我们进入 main 函数，我还没想好名字，所以还是叫 specialFunc。它使用 filterMap 将我们的列表变成 [[1], [0, 1], [1, 2], [0, 1, 2], [0, 2], [0], [1, 2]]，对结果调用 cartesian，将 groupIndices 映射到这些值，然后使用 reduce 查找（第一个) 方差最小的一个。最后它将生成的索引映射回实际值。
同样，我们或许可以清理它并使用值而不是索引，但我首先想知道这是否是您正在寻找的那种行为。
1标准差有更明确的含义，但因为它只是方差的平方根，它将以与方差相同的方式排序，并且不涉及计算平方根。
我正在寻找一个算法名称，最好是一个可以采用数组并以尽可能最好的方式在函数之间拆分它的库。 我不关心复杂性（它适用于非常低的数据集）。 递归检查就足够了。
一个很好的例子是数组：
const list = [{gender: "female"}, {gender: "female"}, {gender: "female"}, {gender: "male"}]
所以如果我们运行它具有特殊功能
specialFunc(list, [(val) => val === 'female', (val) => val === 'male']);
我们会得到这个
[
[{gender: "female"}, {gender: "female"}, {gender: "female"}],
[{gender: "male"}]
]
因为这是我们可以获得的最佳拆分。
但是，如果我们运行它通过这个函数：
specialFunc(list, [(val) => !!val, (val) => val === 'male']);
我会得到这个：
[
[{gender: "female"}, {gender: "female"}, {gender: "female"}],
[{gender: "male"}]
]
“尽可能最好的方式”是指每个数组之间的（数组长度的）数字距离应该是最小的，并且每个数组中的记录数应该是最大的。
我已经搜索了很多 npmjs 和 github 但找不到任何东西。
非常非常感谢！
function splitGroups<T>(items: T[], filters: ((x: T) => boolean)[]) {
let options = filters.map(f => items.filter(f));
let groups = filters.map((_, index) => ({ data: [] as T[], index }));
let res: T[][] = [];
while (options.reduce((partial_sum, a) => partial_sum + a.length, 0) > 0) {
groups.sort((a, b) => a.data.length - b.data.length);
let smallGroup = groups[0];
const smallGroups = groups.filter(g => g.data.length === smallGroup.data.length);
if (smallGroups.length > 1) {
smallGroup = smallGroups[Math.floor(Math.random() * (smallGroups.length - 1))];
}
if (options[smallGroup.index].length === 0) {
res.push(smallGroup.data);
groups = groups.filter(x => x !== smallGroup);
continue;
}
const item = options[smallGroup.index][0];
options = options.map(x => x.filter(y => y !== item));
smallGroup.data.push(item);
}
res = [...res, ...groups.map(x => x.data)];
return res;
}
function accurateSplitGroups<T>(items: T[], filters: ((x: T) => boolean)[], times: number) {
const options: { data: T[][]; diff: number }[] = [];
for (let i = 0; i < times; i++) {
const res = splitGroups(items, filters);
let diffBetweenGroups = 0;
const groupsLens = res.map(x => x.length);
for (let i = 0; i < groupsLens.length; i++) {
for (let j = 0; j < groupsLens.length; j++) {
diffBetweenGroups += Math.abs(groupsLens[i] - groupsLens[j]);
}
}
options.push({ data: res, diff: diffBetweenGroups });
}
return options.sort((a, b) => a.diff - b.diff)[0].data;
}
const items = [{ gender: 'female' }, { gender: 'female' }, { gender: 'female' }, { gender: 'male' }];
const filters = [(x: any) => !!x.gender, (x: any) => !!x.gender];
const res = accurateSplitGroups(items, filters, 100);
const b = res;
我认为我理解这些要求。您有许多要用于对项目进行分组的谓词函数。对于同一项目，多个谓词可能 return 为真，因此可以使用各种分组。您想要找到一个分组，使结果大小的变化最小化。
我觉得你的例子不是很有说服力。我会尝试我自己的。如果您的项目是 8, 6, 7, 5, 3, 0, 9] 并且您有三个谓词：(n) => n < 7、(n) => n > 3 和 (n) => n % 2 == 1，那么 8 只能进入第二组（它是大于 3，但不小于 7 且不为奇数。）6 可以在前两组中的任何一个中，5 可以在其中任何一个中，依此类推，如下所示：
8 6 7 5 3 0 9
[[1], [0, 1], [1, 2], [0, 1, 2], [0, 2], [0], [1, 2]]
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | | | | | | |
| +--|----|--|----+--|--|----+--|----+----|--|------> Group 0 (n => n < 7)
| | | | | | | | |
+-------+----+--|-------+--|-------|---------+--|------> Group 1 (n => n > 3)
| | | |
+----------+-------+------------+------> Group 2 (n => n % 2 == 1)
由于第一个有一个选择，第二个有两个，第三个有两个，依此类推，可能的分区数是1 * 2 * 2 * 3 * 2 * 1 * 2，或48。它们可能看起来像这样：
[// < 7 > 3 odd
[ [6, 5, 3, 0], [8, 7, 9], [] ],
[ [6, 5, 3, 0], [8, 7], [9] ],
[ [6, 5, 0], [8, 7, 9], [3] ],
[ [6, 5, 0], [8, 7], [3, 9] ],
// ... (42 rows elided)
[ [0], [8, 6, 9], [7, 5, 3] ],
[ [0], [8, 6], [7, 5, 3, 9] ]
]
然后，我们需要从中选择分区大小变化最小的分区。我们可以对这个 1 使用统计方差，即值与其平均值距离的平方和，因此 [[6, 5, 3, 0], [8, 7, 9], []]，长度为 4，3 和 0；这有 8.667 的方差。第二个的长度为 4、2 和 1，方差为 4.667。我们最好的可能性是 3、2 和 2，方差为 0.667。所以像 [[6, 5, 0], [8, 7], [3, 9]] 这样的答案是合理的。可能有很多人有类似的行为；下面的实现只是选择第一个。
如果这正确地描述了问题，那么这里是一些我认为可以处理它的代码：
const range = (lo, hi) => Array .from ({length: hi - lo}, (_, i) => i + lo)
const sum = (ns) => ns .reduce ((a, b) => a + b, 0)
const filterMap = (f, m) => (xs) =>
xs .flatMap ((x, i, a) => f (x, i, a) ? [m (x, i, a)] : [])
const cartesian = ([xs, ...xss]) =>
xs == undefined
? [[]]
: xs .flatMap (x => cartesian (xss) .map (ys => [x, ...ys]))
const variance = (ns, avg = sum (ns) / (ns .length || 1)) =>
sum (ns .map (n => (n - avg) * (n - avg)))
const groupIndices = (count) => (xs) =>
Object .values (xs .reduce (
(a, x, i) => ((a [x] .push (i)), a),
Object .fromEntries (range (0, count) .map (n => [n, []]))
))
const specialFunc = (xs, preds) =>
cartesian (xs .map ((x) => filterMap ((pred, i) => pred (x), (_, i) => i) (preds)))
.map (groupIndices (preds .length))
.reduce (
({min, v}, xs, _, __, v2 = variance (xs .map (x => x .length))) =>
v2 < v ? {min: xs, v: v2} : {min, v},
{min: [], v: Infinity}
) .min .map (ys => ys .map (i => xs [i]))
console .log (specialFunc (
[8, 6, 7, 5, 3, 0, 9],
[n => n < 7, n => n > 3, n => n % 2 == 1]
)) //=> [[6, 5, 0], [8, 7], [3, 9]]
.as-console-wrapper {max-height: 100% !important; top: 0}
我们从一些相当标准的实用函数开始。 range 计算一个整数范围，包括底部，不包括顶部，例如，range (3, 12) returns [3, 4, 5, 6, 7, 8, 9 ,10, 11]. sum只是对一个数字数组求和，filterMap结合了过滤和映射，首先测试一个输入是否匹配一个过滤器，如果是，则在将结果放入结果之前转换结果。这个实现是不寻常的，因为过滤器和映射函数不仅需要值，还需要索引和数组属性，如 map 和 filter。我们需要它，因为我们将使用它来收集匹配的索引。 （还有很多其他方法可以做到这一点，但是 filterMap 是一个有用的、可重复使用的函数。） cartesian returns 笛卡尔积数组的数组。例如，cartesian ([1, 2, 3], [true], ['a', 'b']]) 将 return [[1, true, 'a'], [1, true, 'b'], [2, true, 'a'], [2, true, 'b'], [3, true, 'a'], [3, true, 'b']]。最后 variance 计算数字列表的统计方差。
然后我们有一个辅助函数，groupIndices。这可能最容易用一个例子来展示。我们的笛卡尔积的 48 个结果之一将是 [1, 0, 1, 0, 2, 0, 1]，这意味着我们的原始数字（8, 6, 7, 5, 3, 0, 9]，recall）在 1、0、[=30 组中=]、0、2、0 和 1。 groupIndices 采用组数，然后采用笛卡尔组合，并将其转换为 [[1, 3, 5], [0, 2, 6], [4]]，给出映射到每个组的值的 索引 。 （如果我没时间的话，我相信我们可以跳过这个与索引的工作并直接针对值，但这有效。）
现在我们进入 main 函数，我还没想好名字，所以还是叫 specialFunc。它使用 filterMap 将我们的列表变成 [[1], [0, 1], [1, 2], [0, 1, 2], [0, 2], [0], [1, 2]]，对结果调用 cartesian，将 groupIndices 映射到这些值，然后使用 reduce 查找（第一个) 方差最小的一个。最后它将生成的索引映射回实际值。
同样，我们或许可以清理它并使用值而不是索引，但我首先想知道这是否是您正在寻找的那种行为。
1标准差有更明确的含义，但因为它只是方差的平方根，它将以与方差相同的方式排序，并且不涉及计算平方根。