1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

It is pleasing to see such a nice algorithm.

Your algorithm is correct for all inputs except possibly for two corner cases.

  • For example, if we have input = [['A', 1], ['B', 2], ['A', 2], ['B', 3]], then your algorithm will not produce the expected A<=B.
  • For example, if we have input = [['A', 1], ['B', 1], ['A', 1], ['B',1] or input = [['A', 1], ['A', 1], ['B', 1], ['B',1], then your algorithm will not produce the expected A<=B and B<=A.

The issue is not in your algorithm proper but how you define your input and expected result and how you specify the way to sort all endpoints of the intervals. Here is a sample solution.

  • Require that all input intervals are non-degenerate and different.
  • When sorting, break ties with the other endpoint. That is, given A=[1,2] and B=[2,3], when ['A', 2] and ['B',2] are compared, we must put the former before the latter since 1 < 3.

By the way, you can just use const item of input instead of const item of input.reverse(). Also, you may use ${closed.slice(l[0][0],l[0][1])} <= ${l[1]} instead of ${closed.slice(l[0][0],l[0][1])}:${l[1]} since you use "<=" to define the relation. You should get a slightly prettier output.


Last but not least, Code View Stack Exchange should probably be a better place to post this kind of question.

$\endgroup$
  • $\begingroup$ "For example, if we have input = [['A', 1], ['B', 2], ['A', 2], ['B', 3]], then your algorithm will not produce the expected A<=B." Yes, I forgot to specify this. Opening a range should come before closing one in the iterator. $\endgroup$ – epiqueras Oct 22 '18 at 12:05
  • $\begingroup$ "For example, if we have input = [['A', 1], ['B', 1], ['A', 1], ['B',1] or input = [['A', 1], ['A', 1], ['B', 1], ['B',1], then your algorithm will not produce the expected A<=B and B<=A." Actually, B and A are complementary in this case, and if you follow the ordering from my previous comment, you get ":B, A", which is correct. $\endgroup$ – epiqueras Oct 22 '18 at 12:06
  • $\begingroup$ "It is pleasing to see such a nice algorithm." Thanks! $\endgroup$ – epiqueras Oct 22 '18 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.