集合不包含一个地方a⊆b和b是集合中

Question

我需要无视包含在其他元素的集合：

Picky(Set(1, 2)) + Set(1) should equal(Picky(Set(1, 2))) 

Picky(Set(1)) + Set(1, 2) should equal(Picky(Set(1, 2))) 

Picky(Set(1, 3)) + Set(1, 2) should equal(Picky(Set(1, 3), Set(1, 2))) 

Picky(Set(1, 2), (Set(1))) should equal(Picky(Set(1, 2))) 

其实我有一个解决方案

case class Picky[T] private(sets: Set[Set[T]]) { 
    def +(s: Set[T]): Picky[T] = Picky(Picky.internalAddition(this.sets, s)) 
} 

object Picky { 
    def apply[T](sets: Set[T]*): Picky[T] = 
    Picky((Set[Set[T]]() /: sets)(internalAddition(_, _))) 

    private def internalAddition[T](c: Set[Set[T]], s: Set[T]): Set[Set[T]] = 
    if (c.exists(s subsetOf _)) c else c.filterNot(_ subsetOf s) + s 
} 

但是我想知道是否已经有一个包含这个概念的集合，因为我试图做的听起来有点像一个具有一种还原函数的集合，就像下面一个接受worse函数的虚构集合（在我们的具体实现中为情况）：

PickySet(){(a, b) => a subset b} 

如为任何的元件（A，B）如果worse(a, b)返回true，a将被丢弃

为了明确与集的差异，一组将是PickySet的一种特殊情况：

PickySet(){_ == _} 

Answer 1

我不认为你会找到一个方便的现成的实现这个集合，但你可以让你更通用一点，通过使用scala.math.PartialOrdering和事实，集是部分排序的事实子集关系。

首先用于定义Picky。实际上，你想要的只是一个容器，只能容纳maximal elements，其中没有元素相对于对方排序，并且所有较小的元素都已被删除。

class Picky[A: PartialOrdering] private(val xs: Seq[A]) { 
    def +(y: A): Picky[A] = new Picky(Picky.add(xs, y)) 
    override def toString = "Picky(%s)".format(xs.mkString(", ")) 
} 

object Picky { 
    def apply[A: PartialOrdering](xs: A*): Picky[A] = 
    new Picky(xs.foldLeft(Seq.empty[A])(add)) 

    private def add[A](xs: Seq[A], y: A)(implicit ord: PartialOrdering[A]) = { 
    val notSmaller = xs.filterNot(ord.lteq(_, y)) 
    if (notSmaller.exists(ord.lteq(y, _))) notSmaller else notSmaller :+ y 
    } 
} 

接着用于套部分排序，这是仅定义如果所述集合中的一个是另一个的子集（可能是平凡）：

implicit def subsetOrdering[A] = new PartialOrdering[Set[A]] { 
    def tryCompare(x: Set[A], y: Set[A]) = 
    if (x == y) Some(0) 
    else if (x subsetOf y) Some(-1) 
    else if (y subsetOf x) Some(1) 
    else None 

    def lteq(x: Set[A], y: Set[A]) = 
    this.tryCompare(x, y).map(_ <= 0).getOrElse(false) 
} 

的tryCompare以下等效定义可以想见快一点：

def tryCompare(x: Set[A], y: Set[A]) = { 
    val s = (x & y).size 
    if (s == x.size || s == y.size) Some(x.size - y.size) else None 
} 

现在我们得到想要的结果：

scala> Picky(Set(1, 2)) + Set(1) 
res0: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 2)) 

scala> Picky(Set(1)) + Set(1, 2) 
res1: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 2)) 

scala> Picky(Set(1, 3)) + Set(1, 2) 
res2: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 3), Set(1, 2)) 

scala> Picky(Set(1, 2), (Set(1))) 
res3: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 2)) 

请注意，我们可以很容易地定义一个替代的偏序排列，它将给出Picky普通旧集合语义（即只有相等的东西相对于彼此排序，并且它们总是相等的）。