Is this algorithm for partial ordering of sets complete and sound?
-
05-11-2019 - |
Question
I need to build a partial order tree of sets for analysis.
Where the order is defined as A <= B <=> for all x in A, y in B, x <= y
.
I realized that if I pre-sort all the maximal and minimal elements of the sets, like this:
// A [1,3]
// B [2,4]
// C [3,5]
// D [6,7]
// E [8,9]
// F [10,11]
const input = [['A', 1], ['B', 2], ['C', 3], ['A', 3], ['B', 4], ['C', 5], ['D', 6], ['D', 7], ['E', 8], ['E', 9], ['F', 10], ['F', 11]]
I can achieve it in O(n)
, with the following algorithm:
let i = 0
const closed = []
const opened = {}
const lists = []
for (const item of input.reverse()) {
if (!opened[item[0]]) { // Opening the range.
// May need to create a new list.
if (i <= closed.length) {
lists.push([[i - 1, closed.length], []])
i = closed.length + 1
}
// Add to list.
lists[lists.length - 1][1].push(item[0])
opened[item[0]] = true
} else // Closing the range.
closed.push(item[0])
}
This is javascript and you can pretty print the result like so:
console.log(lists.map(l => `${closed.slice(l[0][0],l[0][1])}:${l[1]}`).join('\n'))
// :F
// F:E
// E:D
// D:C,B,A
Are there orders for which this might not work?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange