标签: poset

在阅读Bartosz 为程序员提供的优秀类别理论时,我陷入了第二个练习,即第二个练习,它处理了网络中的产品.鉴于一个poset,

    b   e
  ?   ?   ?
a ? c   f ? h
  ?   ?   ?
    d   g

如何在分类意义上定义产品？什么是两个对象的产品分类？那副产品呢？

我正在寻找一个数据结构的Java实现,它包含一个元素集合,其中定义了一个部分排序,并允许一个元素以某种拓扑顺序迭代这些元素(任何可能的排序都很好;最好是一个稳定的订购作为集合的内容更改).

理想情况下,它将实现一个Collection<E>,Set<E>或SortedSet<E>接口,并支持接口上的所有方法.在指定总排序方面,可以使用a来实例化集合Comparator<E>,并且ClassCastException如果被比较的两个元素没有相对于彼此排序,则比较器可以抛出异常(？).作为奖励,如果插入的元素会产生排序异常(元素的有序图中的循环),它将抛出异常.

所以是的,我想要的是一个拓扑排序,但是我想要一个集合对象,它在每次插入/删除时保持排序顺序,类似于SortedSet如何按排序顺序维护集合.

这样的事情存在吗？在一些开源库中？

参考文献:

http://en.wikipedia.org/wiki/Partially_ordered_set

http://en.wikipedia.org/wiki/Topological_sorting

更新

在我意识到我的要求的性能影响(以及我无法解决的各种其他问题,使用poset)之后,我最终采用了不同的方法解决了我的问题,我不需要一个poset.依靠比较器来确定元素之间的顺序意味着对于元素插入,我必须针对每个现有元素查询比较器,每次插入花费O(n).

如果性能不是很重要(确实如此),并且如果元素的数量被限制在合理的范围内(事实并非如此),我想我会采用Willie建议的方法,尽管可能使用我自己的图形实现和拓扑排序实现以最小化依赖性.

有大量的排序算法,但大多数只能在完全有序的集合上工作,因为他们认为任何两个元素都是可比较的.但是,是否有任何好的算法用于排序posets,其中一些元素是无法比较的？也就是说,由于从偏序集绘制的元素的集合S,什么是输出的最好方式排序X ₁,X ₂,...,X _ñ例如,如果X _我 ≤X _Ĵ,I≤J′

我有一个偏序集,说A = [x1, x2, ...],这意味着每一个xi和xj集合中的,(恰好)的四种可能性之一为真:xi < xj,xi == xj,xi > xj,或xi与xj所无法比拟的.

我想找到的最大元素(即,这些元素xi是针对那些还没有元素xj用xi < xj).什么是有效的算法(最小化比较次数)？我尝试构建DAG并进行拓扑排序,但只是构建图形需要进行O(n ^ 2)次比较,这太多了.

我在Python中这样做,但如果你不知道它我可以读其他语言,或伪代码.

我有一些列表中包含可变数量的元素.每个列表都已排序,但排序算法未知.我想将列表合并到一个大列表中,该列表包含相同顺序的所有列表,没有重复.

示例输入:

1. XS,M,L,XL
2. S,M,XXL
3. XXS,XS,S,L

预期结果:

• XXS,XS,S,M,L,XL,XXL

通过匹配输入序列来获得预期结果,以便以正确的顺序获得包含每个输入序列的元素的合并结果,如下所示:

    XS   M L XL
       S M      XXL
XXS XS S   L
-------------------
XXS XS S M L XL XXL

如果存在具有不明确位置的元素,则该函数应通知.在这里,它将是XXL(它可以保持在M,L或XL之后)并且我需要在XL之后手动指定其位置(因为在这里我知道排序算法并且可以帮助).我想要定义每两个元素的对,每个元素按照原始列表的顺序排列.从这个可以建立完整的列表.

如何有效地枚举有限集上的所有偏序？

我想检查是否存在具有指定属性的部分订单.为了检查这一点,我将用蛮力来枚举小有限集上的所有可能的偏序.

我有一个使用语句块的程序EDSL.

尽管语句之间可能存在依赖关系,但这些语句没有按特定顺序添加到块中.

但是,在编译EDSL期间,我需要确保语句按依赖顺序排序,例如

B := A
C := B
E := D

由于并非所有语句都具有依赖性,因此没有总顺序(例如,E := D上面是独立的,可以放在任何地方).没有循环依赖关系,因此列表排序应该是可能的.

我试图通过使用Data.List.sortBy和定义Ordering哪些将返回EQ意味着语句没有依赖性来破解解决方案.这适用于一些示例,但不适用于一般情况,例如,订购以下内容无效:

C := B                           B := A
D := C    = should produce =>    C := B
B := A                           D := C

这是因为默认排序插入排序并且只确保插入的项目小于或等于下一个.

我已经在互联网上搜索了Poset实现,但没有找到任何适用的东西:

altfloat:Data.Poset定义Ordering = LT | GT | EQ | NC(NC非可比的),这是好的,但所提供的sort呈NaN样不具有可比性的项目,只是抛出他们离开.

logfloat:Data.Number.PartialOrd类似于上面的除了用途Maybe Ordering,我没有在包中的任何地方看到排序功能.

Math.Combinatorics.Poset我还没弄清楚如何使用它或它是否适用.

下面是一个包含绑定和非绑定语句的最小示例.非biniding语句的顺序很重要,并且它们必须保持原始顺序(即排序需要与没有依赖关系的语句保持稳定).

我希望有一个简单的解决方案,而不使用完整的依赖图...

module Stmts where …

在尝试分类算法时遇到了以下算法问题.元素被分类为多层次结构,我理解为具有单根的poset.我必须解决以下问题,这看起来很像设置封面问题.

我在这里上传了我的Latex-ed问题描述.

设计满足1和2的近似算法非常简单,只需从G的顶点开始并"向上走"或从根开始并"向下走".假设您从根开始,迭代地展开顶点,然后删除不必要的顶点,直到您至少有k个子格.近似界限取决于顶点的子节点数,这对我的应用程序来说是可以的.

有谁知道这个问题是否有正确的名称,或者问题的树版本？我有兴趣知道这个问题是否是NP难的,也许有人想要一个好的NP难问题来减少或者有一个多项式算法来解决这个问题.如果你们都收取了百万美元的价格.;)

我正在根据 SQLAlchemy 实现一种具有Partially Ordered Set数学特征的结构，其中我需要能够一次添加和删除一个边。

在我目前的最佳设计中，我使用了两个邻接表，一个是分配表（大约是哈斯图中的边），因为我需要保留哪些节点对被明确设置为有序，另一个邻接表是传递的关闭第一个，以便我可以有效地查询一个节点是否相对于另一个节点排序。现在，每次在分配邻接列表中添加或删除边时，我都会重新计算传递闭包。

它看起来像这样：

assignment = Table('assignment', metadata,
    Column('parent', Integer, ForeignKey('node.id')),
    Column('child', Integer, ForeignKey('node.id')))

closure = Table('closure', metadata,
    Column('ancestor', Integer, ForeignKey('node.id')),
    Column('descendent', Integer, ForeignKey('node.id')))

class Node(Base):
    __tablename__ = 'node'
    id = Column(Integer, primary_key=True)

    parents = relationship(Node, secondary=assignment,
        backref='children',
        primaryjoin=id == assignment.c.parent,
        secondaryjoin=id == assignment.c.child)

    ancestors = relationship(Node, secondary=closure,
        backref='descendents',
        primaryjoin=id == closure.c.ancestor,
        secondaryjoin=id == closure.c.descendent,
        viewonly=True)

    @classmethod
    def recompute_ancestry(cls.conn):
        conn.execute(closure.delete())
        adjacent_values = conn.execute(assignment.select()).fetchall()
        conn.execute(closure.insert(), floyd_warshall(adjacent_values))

其中floyd_warshall()是同名算法的实现。

这导致我遇到两个问题。首先是它似乎不是很有效，但我不确定我可以使用什么样的算法来代替。

第二个更多是关于Node.recompute_ancestry()每次分配发生时必须显式调用的实用性，并且只有在分配被刷新到会话中并具有适当的连接之后。如果我想查看反映在 ORM …

我把它作为算法最终的最后一个问题(现已完成):

给定一组(x,y)点P,令M(P)为P上给出以下部分排序的最大点集:

(x,y) < (x',y') if and only if x < x' and y < y'.

从而:

M({(0,0),(1,1)})={(1,1)}
M({(0,0),(0,1),(1,0)})={(0,1),(1,0)}

给出计算M(P)的算法,其时间复杂度为O(nh),O(n log n)和O(n log h)(其中n = | P |且h = | M(P)|)

我的O(nh)算法:

Declare M as a set of points
foreach p in P:
  addP = true
  foreach m in M:
    if(p < m):
      addP = false
      break
    if(m < p):
      M.remove(m)
  if(addP)
    M.add(p) //doesn't add if M contains p
return M …