poset

4熱度

2回答

我使用SQLAlchemy實現了一個具有Partially Ordered Set的數學特性的結構，其中我需要能夠一次添加和刪除一條邊。我使用兩個鄰接列表，一個是賦值列表（Hass圖中的近似邊），因爲我需要保留哪些對明確設置爲有序，而另一個鄰接list是第一個的傳遞閉包，所以我可以高效地查詢一個節點是否相對於另一個節點進行排序。現在，每當向分配鄰接列表中添加或刪除邊緣時，我都會重新計算傳遞閉包。

2熱度

1回答

一個poset的元素的概率是最大的？

給定一個partially-ordered set（poset），假定所有線性擴展的可能性相同，估計線性擴展中元素爲最頂級的概率的算法是什麼？

5熱度

1回答

算法計算最大點在點集

我有這個作爲一個算法最終（現已完成）的最後一個問題：給定一組（X，Y）點P，讓M（P）是集合給定上P上的以下部分排序maximal點： (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)} 給出了計算具有時間復

13熱度

1回答

產品和副本產品

在閱讀Bartosz優秀的Category theory for Programmers時，我陷入了第二個練習中，該練習涉及到posets中的產品。給定一個poset， b e ↗ ⤭ ↘ a → c f → h ↘ ⤭ ↗ d g 如何定義產品的分類意義？什麼是由兩個對象的產品分類的？那副產品呢？

1熱度

1回答

Poset迭代次序/用於部分有序集合的自定義迭代器實現

我在java中創建了一個部分有序集作爲抽象數據類型，並且我必須創建一組數字的迭代器版本以及關係的迭代器。現在對於元素，我使用了HashSet的整數，對於關係，我使用了一個ArrayList對（對是我創建的一個類，它需要2個整數作爲參數，基本上就像（x，y））。我需要做2個迭代器，一個用於s，另一個用於r，但它們必須遵循某個順序，如果（x，y）屬於R，則s的迭代器在返回y之前應返回x y 2.如果（

9熱度

3回答

排序一個poset？

這裏有大量的排序算法，但其中大多數只適用於完全有序的集合，因爲他們假定任何兩個元素都是可比較的。但是，有沒有什麼好的算法可以用來排序posets，其中一些元素是無法比擬的？也就是說，由於從偏序集繪製的元素的集合S，什麼是輸出的最好方式排序X ，X ，...，X ñ這樣如果x 我 ≤ X j，i ≤ j？

2熱度

2回答

創建類關係

給定一個模塊數組，返回描述模塊之間規範化（最小）排序關係的數組的最佳方法是什麼？數組中的每個元素都應該是具有子父母關係的模塊對的數組。每對中的子女父母訂單很重要，但雙方之間的訂單無關緊要。規範化排序意味着無論從傳遞性中派生出什麼都應該從數組中排除。例如，給定[Object, Comparable, Float, Fixnum, Integer]，答案將是： [ [Float, Obje

3熱度

1回答

部分有序集（DAG）中的反鏈

任何人都可以告訴是否存在用於查找部分有序集中大小爲k的反鏈的P時間算法嗎？（或DAG）我在網上找到的所有資源都涉及找到最大的反鏈。

4熱度

1回答

找到一個序集的子集

問題的最大因素是：給定一個序集的子集S找到S. 的最大元素例如，考慮偏序集的HASS圖中http://ndp.jct.ac.il/tutorials/Discrete/node34.html。鑑於它的一個子集，例如：{12,2,8}，最大元素是12和8. 我不知道我是否會精確地描述問題。我認爲這個問題可能涉及到傳遞閉包的一些排序或計算，但我有點困惑。你能給我一些快速算法的方法嗎？我想保留在O（