algorithm - 将序列切割成两个同质部分

Question

我想将一系列类分成两部分，每个部分尽可能“同质”:

• 一个部分应包含尽可能少的类
• 部件长度相似更好。

结果示例:

[A, A, A, A, A, B, B, B, B, B] -> [A, A, A, A, A] + [B, B, B, B, B]
[A, A, A, B, B, B, B, B, B, B] -> [A, A, A] + [B, B, B, B, B, B, B]
[A, B, B, B, B, A, A, A, A, A] -> [A, B, B, B, B] + [A, A, A, A, A]
[A, B, C, A, B, D, D, D, D, D] -> [A, B, C, A, B] + [D, D, D, D, D]
[A, A, B, B, C, C, C, D, D, D] -> [A, A, B, B] + [C, C, C, D, D, D]
[B, B, A, A, A, A, B, B, B, B] -> [B, B, A, A, A, A] + [B, B, B, B]
[A, A, A, B, B, B, B, C, B, B] -> [A, A, A] + [B, B, B, B, C, B, B]

我无法将这些标准合并为一个分数来确定最佳剪辑。 我尝试了基于 entropy 的公式(尝试所有可能的切割，计算两个部分的熵，并尝试最小化最大值/平均值)或最大化每个类别的频率的标准(一个部分更好，它包含所有出现的〜0％或〜100％一个类)。

这些方法不考虑序列的顺序。结果还不错，但仍然存在每种评分方法都会导致“不自然”结果的情况(其中一个元素的一部分 + 序列其余部分的评分还不错，...)

Answer 1

有两个成本需要最小化:

• 成本1:分割点距数组中心的距离
• 成本 2:左组中不同项目的数量加上右组中不同项目的数量。您可以使用 HashSet 来有效地保存不同值的计数。

现在您需要做出选择:这些成本的相关重要性是什么？第一个成本比第二个成本更重要还是反之亦然？另外，这些成本是否应该被视为线性增加，还是以越来越快的速度增长？这些问题的答案将为如何将这两项成本汇总为一项最终成本提供线索。

例如，您可以说距离中心 4 个单位的分割比距离中心 2 个单位的分割差两倍；或者你可以说它是二次的:第一次 split 比第二次 split 糟糕 4 倍。正如您所说，第一个元素之后的分割是“不自然的”，我猜您更喜欢第一个成本的二次(甚至更高的幂)。

对于第二个成本也可以这样做。

示例

为了说明这一点，这里有一个您可以争论在哪里拆分的情况:

[A, B, C, C, C, C, C, C, B, C]

哪种剪辑效果更好？

[A, B] + [C, C, C, C, C, C, B, C]

或者:

[A] + [B, C, C, C, C, C, C, B, C]

如果第一个成本更重要，那么第一个解决方案可能会更好，如果第二个成本更重要，那么它将是第二个解决方案。

如果我们认为第一个解决方案更好，那么想知道在第一个 C 处进行分割的决定不再被认为是好的之前，可以在输入的开头插入多少额外 A？

如果我们认为第二种解决方案更好，那么想知道在“C block ”中可以插入多少额外 C 值，直到决策发生改变(如果有的话)？

提案

一个可能的公式是:

        成本 = 成本₁² + 成本₂²

下面是一个 JavaScript 实现，显示了您提供的示例的结果:

function optimalSplit(a) {
    // Store a count of distinct elements at the right for each split
    let right = new Set;
    let rightSize = [];
    for (let i = a.length - 1; i > 0; i--) {
        right.add(a[i]); // only adds the value when not yet present
        rightSize[i] = right.size;
    }

    // Do the same for the left side, and calculate the final cost for each split
    let left = new Set;
    left.add(a[0]);
    let k; // the optimal index at which to split
    let minCost = Infinity;
    for (let i = 1; i < a.length; i++) {
        let cost = (a.length/2 - i)**2 + (left.size + rightSize[i])**2;
        if (cost < minCost) {
            minCost = cost;
            k = i;
        };
        left.add(a[i]);
    }
    return [a.slice(0, k), a.slice(k)];
}

// Examples
let testCases = [
    ["A", "A", "A", "A", "A", "B", "B", "B", "B", "B"],
    ["A", "A", "A", "B", "B", "B", "B", "B", "B", "B"],
    ["A", "B", "B", "B", "B", "A", "A", "A", "A", "A"],
    ["A", "B", "C", "A", "B", "D", "D", "D", "D", "D"],
    ["A", "A", "B", "B", "C", "C", "C", "D", "D", "D"],
    ["B", "B", "A", "A", "A", "A", "B", "B", "B", "B"],
    ["A", "A", "A", "B", "B", "B", "B", "C", "B", "B"]
];

for (let input of testCases) {
    console.log(JSON.stringify(optimalSplit(input)));
}