Author |
Topic: remove partial orderd elements from a array (Read 521 times) |
|
cuckoo
Junior Member
Gender: 
Posts: 57
|
 |
remove partial orderd elements from a array
« on: Aug 30th, 2007, 3:06am » |
 Quote  Modify
|
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?
|
| « Last Edit: Aug 30th, 2007, 3:37am by cuckoo » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: remove partial orderd elements from a array
« Reply #1 on: Aug 30th, 2007, 4:30am » |
Quote Modify
|
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(n2) 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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print