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

Question

我想将 class 的序列分成两部分，每个部分尽可能 "homogeneous" :

一个部分应该包含尽可能少的 classes
如果零件的长度相似就更好了。

结果示例：

[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 的公式（尝试所有可能的切割，计算两个部分的熵，并尝试最小化 max/average）或最大化每个 class 频率的标准（一部分更好的是它包含 ~0% 或 ~100% 的所有出现的 classes）。

这些方法不考虑序列的顺序。结果还可以，但仍然存在每种评分方法都会导致 "unnatural" 结果的情况（只有一个元素的部分 + 序列其余部分的评分还算可以，...）

Answer 1

有两个成本可以最小化：

成本 1：拆分距阵列中心的距离
成本 2：左组中不同项目的数量加上右组中不同项目的数量。您可以使用 HashSet 有效地保持不同值的计数。

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

例如，您可以说距离中心 4 个单位的分割比距离中心 2 个单位的分割差两倍；或者你可以说它是二次方的：第一次分裂比第二次分裂差 4 倍。正如您所说的第一个元素之后的拆分是 "unnatural"，我猜您更喜欢第一个成本的二次方（或更高次方）。

第二笔费用也可以这样做。

例子

为了说明，这里是一个你可以争论在哪里拆分的案例：

[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 处拆分之前，可以在输入的开头插入多少 extra A算不算好？

如果我们考虑第二种解决方案更好，那么想知道有多少 extra C 值可以插入 "C-block" 直到决定改变（如果有的话）？

提案

一个可能的公式是：

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

这是一个 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)));
}

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

Cut a sequence into two homogeneous parts

algorithm

sequence

例子

提案