wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> remove partial orderd elements from a array
        
(Message started by: cuckoo on Aug 30^th, 2007, 3:06am)

Title: remove partial orderd elements from a array
Post by cuckoo on Aug 30^th, 2007, 3:06am

In the past few months, I came across several similar problems on other forums. The problems can be generalized as follows:
Given an array of elements, say a[1..n], a partial order "<" is defined on the elements. If a[i]<a[j], then you must remove a[j] from the array. Your task is to remove all such a[j]'s so that for any i and j, neither a[i]<a[j] nor a[j]<a[i].

The partial order here may be interpreted as division "|", or set inclusion, etc.

Especially, when the partial order is division "|", this problem is very similar to the sieve method for primes. The time complexity of sieve method is O(nloglog(n)).

My question is:
(1)When the partial order is set inclusion, Can the above problem be solved in O(nlog(n)) time?

(2)Can the above problem be solved in O(nlog(n)) time regardless of the partial order?

Title: Re: remove partial orderd elements from a array
Post by towr on Aug 30^th, 2007, 4:30am

I think 1) would be difficult to do in O(n log(n) time.
consider
a[0]={2,3,4}
a[1]={1,3,4}
a[2]={1,2,4}
a[3]={1,2,3}
a[4]={1,2,3,4}

Even if you somehow know that a[4] is the only candidate the other can be a subset of, it would take O(n²) to check, unless perhaps you have some perfect incremental hash (i.e. the hash has a similar partial order that hash(X) < hash(Y) iff X < Y).