scala - 按边距分组

Question

我有一个 Int 数字序列:

val numbers = Seq(5, 3, 4, 1)

我需要根据它们的差异对它们进行分组。差异必须小于或等于某个阈值，在本例中设为 2。所以可能的组是:

• (5, 3, 4) (1)
• (1, 3) (5, 4)

我真的不在乎我会得到这些群体中的哪一个。每个元素允许使用一次。我还需要保留索引，因此在分组之前我需要一个 zipWithIndex。

有没有一种巧妙的方法来进行这种分组？

Answer 1

那好吧。算法思路:

获取numbers 中的下一个元素。检查它是否属于以前创建的组。如果是，请将其添加到该组。如果不是，请使用该元素添加一个新组。我使用 IndexedSeq 因为我希望索引为 O(1)。

它有点长，但我现在想不出更好的东西。我希望我正确地理解了您对“差异”的看法。

val numbers = Seq(5, 3, 4, 1)

def group(seq: Seq[Int], treshold: Int) = seq.zipWithIndex.foldLeft(IndexedSeq.empty[IndexedSeq[(Int,Int)]])((result, elem) =>  {
    (0 until result.size).find(
        i => result(i).forall(num => (num._1 - elem._1).abs <= treshold)).map(
            i => result.updated(i, result(i) :+ elem))
                .getOrElse(result :+ IndexedSeq(elem))
})

println(group(numbers, 2)) //result Vector(Vector((5,0), (3,1), (4,2)), Vector((1,3)))

编辑忘记了你想要zipWithIndex