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
scroll top