Author |
Topic: Finding a Permutation (Read 3244 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Re: Finding a Permutation
« Reply #25 on: Nov 5th, 2003, 10:25am » |
 Quote  Modify
|
Barukh, let me help you a little  .
Lets recap what we have on the 2nd question (e.g. the "follower"):
As you suggested, we divided the set of numbers into n2 bins. Every time that we have "transfered" a number into bini, we added an element with a key valued i to the list (e.g. set) of bins that are in use. At the end of this stage we have bins that hold the all the initial numbers (lets forget about them) and a list of the bins that are in use. So practically, we have reduced the initial problem to the problem of sorting a list/array of size n that holds numbers (maybe duplicate) from the range of {0, ..., n2-1}.
So...
Barukh, now it's your turn to complete the algorithm.
|
| « Last Edit: Nov 5th, 2003, 10:26am by Dudidu » |
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
|
Re: Finding a Permutation
« Reply #26 on: Nov 6th, 2003, 2:22am » |
Quote Modify
|
on Nov 5th, 2003, 10:25am, Dudidu wrote:| So ... we have reduced ... to the problem of sorting a list/array of size n that holds numbers (maybe duplicate) from the range of {0, ..., n2-1}. |
|
Yes, I got it. And what is most obvious way to do it (at least for me)? Radix sort! 
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Finding a Permutation
« Reply #27 on: Nov 6th, 2003, 3:22am » |
Quote Modify
|
on Nov 6th, 2003, 2:22am, Barukh wrote:Yes, I got it. And what is most obvious way to do it (at least for me)? Radix sort!
|
|
There is another way to do it that uses counting sort (http://www.nist.gov/dads/HTML/countingsort.html)... but nevermind (it seems that this question has already been "pushed to the limit" ).
|
|
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Finding a Permutation
« Reply #28 on: Nov 6th, 2003, 5:39am » |
Quote Modify
|
on Nov 6th, 2003, 3:22am, Dudidu wrote:
Let's push the limit a little further 
I think this is O(n^2) because you are sorting numbers in the range 0..n^2-1.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Finding a Permutation
« Reply #29 on: Nov 6th, 2003, 6:06am » |
Quote Modify
|
on Nov 6th, 2003, 5:39am, DH wrote:| I think this is O(n^2) because you are sorting numbers in the range 0..n^2-1. |
|
DH, please pay attention that I wrote "uses counting sort", so counting sort is not a "stand alone" procedure to answer this problem. However, I must admit  that the this solution uses ideas taken from the radix sort (So, some may say that this is an extension of radix sort).
Sorry if this was misleading...
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding a Permutation
« Reply #30 on: Nov 6th, 2003, 11:20am » |
Quote Modify
|
on Nov 6th, 2003, 5:39am, DH wrote:| Let's push the limit a little further . |
|
And let me push it further still
Using the radix sort idea, it is possible in linear time to deliver a permutation with the sum of absolute differences [le] 1 + 1/nk for every constant k.
An amazing problem!
|
| « Last Edit: Nov 6th, 2003, 11:21am by Barukh » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print