Author |
Topic: Finding a Permutation (Read 3241 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Finding a Permutation
« on: Oct 29th, 2003, 6:05am » |
 Quote  Modify
|
Given n real numbers x1,...,xn where each xi[in][0,1], devise an algorithm that will output a permutation of them ([sigma]) such that [sum]i=2n |x[smiley=subsigma.gif](i) - x[smiley=subsigma.gif](i-1)| [le] 2.
Hint: An algorithm that sorts x1,...,xn is not efficent enough.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Finding a Permutation
« Reply #1 on: Oct 29th, 2003, 7:39am » |
Quote Modify
|
::I can see why sorting isn't efficient enough, since then the sum is smaller or equal to 1, which is better than asked..
So partly sorting it is sufficient, like sorting the front and the back half 
But you probably want O(n) (or better), instead of O(n log(n)) with a better constant::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Finding a Permutation
« Reply #2 on: Oct 30th, 2003, 12:13am » |
Quote Modify
|
towr,
when I said in my hint that "an algorithm that sorts ... is not efficent enough" I didn't mean to say that it doesn't solve the problem. I meant to indicate that O(nlogn) time complexity isn't good enough (i.e. I'm looking for an algorithm with a better time complexity).
Sorry if this wasn't comprehensible  .
|
| « Last Edit: Oct 30th, 2003, 12:13am by Dudidu » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding a Permutation
« Reply #3 on: Oct 30th, 2003, 1:31am » |
Quote Modify
|
I know it solves the problem, but it does much better than asked, so it's too powerfull a method, and something weaker is sufficient..
I was just wondering how much more efficient you wanted..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Finding a Permutation
« Reply #4 on: Oct 30th, 2003, 3:08am » |
Quote Modify
|
on Oct 30th, 2003, 1:31am, towr wrote:| I was just wondering how much more efficient you wanted.. |
|
I'm looking for a O(n) time complexity algorithm.
Hope this helps... 
|
| « Last Edit: Oct 30th, 2003, 3:09am by Dudidu » |
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Finding a Permutation
« Reply #5 on: Oct 30th, 2003, 6:18am » |
Quote Modify
|
::
Split the numbers in n sets. For the ith set all numbers are greater than or equal to (i-1)/n and lower than i/n. if present , 1 belongs to the nth set. For each set find the maximum and the minimum. To get the permutation list the numbers from all sets starting with the 1st and ending with the nth set. Inside a set first list the minimum then all other numbers ( the order does not matter ) then list the maximum from that set.
There will be 2 kind of terms in our sum:
1: the numbers belong to the same set -> the term is <=1/n
2: the numbers belong to different sets -> there are no other numbers between those 2 numbers that appear in the respective term because the first number is the maximum in some set and the next number is the minimum in the following non empty set.
The sum of all terms of type 1 is < 1. The sum of all terms of type 2 is <=1.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Finding a Permutation
« Reply #7 on: Oct 30th, 2003, 9:43am » |
Quote Modify
|
Well done DH !!!
A correct solution  !
but can you solve the "follower"...
Given n real numbers x1,...,xn where each xi[in][0,1], devise an algorithm that will output a permutation of them ([sigma]) such that [sum]i=2n |x[smiley=subsigma.gif](i) - x[smiley=subsigma.gif](i-1)| [le] 1 + 1/n.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding a Permutation
« Reply #8 on: Oct 30th, 2003, 9:49am » |
Quote Modify
|
I would like to join Dudidu in praising DH's solution. As for the follower:
[smiley=blacksquare.gif]
If the interval [0,1] is divided into K sub-intervals, then - using the same reasoning as DH's - the sum will not exceed 1 + n/K. So, take K = n2.
[smiley=blacksquare.gif]
And the last but not the least: thanks, Dudidu, for this brilliant puzzle!
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Finding a Permutation
« Reply #9 on: Oct 30th, 2003, 10:00am » |
Quote Modify
|
Barukh,
Your solution for the follower is a little bit problematic:
If you take K = n2, you have (of course) n2 bins. Thus, when you want to "build" your permutation you will need to look in all the bins, and this can take O(n2) time complexity.
So, how can you deal with this minor ( ) problem?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding a Permutation
« Reply #11 on: Oct 30th, 2003, 10:50am » |
Quote Modify
|
I didn't have time to answer (seems the posts are coming with a speed of light ).
Anyway, yours is a good point, Dudidu! I am not sure I understand what towr had in mind, but that's what I have: [smiley=blacksquare.gif]Divide all the bins into n sets, n bins in each. When generating the permutation, scan the sets first, then the bins in non-empty sets. Because there are only n elements, the ocmplexity cannot exceed O(n).[smiley=blacksquare.gif]
Does it make sense?
|
| « Last Edit: Oct 30th, 2003, 10:51am by Barukh » |
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Finding a Permutation
« Reply #12 on: Oct 30th, 2003, 3:04pm » |
Quote Modify
|
on Oct 30th, 2003, 10:50am, Barukh wrote:I didn't have time to answer (seems the posts are coming with a speed of light ).
Anyway, yours is a good point, Dudidu! I am not sure I understand what towr had in mind, but that's what I have: [smiley=blacksquare.gif]Divide all the bins into n sets, n bins in each. When generating the permutation, scan the sets first, then the bins in non-empty sets. Because there are only n elements, the ocmplexity cannot exceed O(n).[smiley=blacksquare.gif]
Does it make sense? |
|
That would not work because the number of non-empty bins ( on the first level ) is generally O(n) so the complexity is still O(n^2) .
But I think the following works:
Splitting the numbers into bins ( or , better said , buckets ) is actually bucket sort. What we need is to sort the numbers based on their first 2 digits ( in base n ). This is done O(n) using bucket sort.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding a Permutation
« Reply #13 on: Oct 31st, 2003, 12:36am » |
Quote Modify
|
on Oct 30th, 2003, 3:04pm, DH wrote:| That would not work because the number of non-empty bins ( on the first level ) is generally O(n) so the complexity is still O(n^2) . |
|
DH, I think we are addressing different issues. Actually, the solution consists of 2 parts:
1. Splitting the numbers into bins (or buckets).
2. Generating the permutation out of the bins.
I think Dudidu's question was about the second part: because there are n2 bins, we cannot just organize them as an array, since then traversing it will take O(n2) time. My approach, I still believe, does remove this obstacle.
Quote:| But I think the following works: |
|
Your post, I think, shows how to perfrom efficiently the first part. But, maybe I am wrong...
|
|
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Finding a Permutation
« Reply #14 on: Oct 31st, 2003, 2:14am » |
Quote Modify
|
Quote:
....
I think Dudidu's question was about the second part: because there are n2 bins, we cannot just organize them as an array, since then traversing it will take O(n2) time. My approach, I still believe, does remove this obstacle.
Your post, I think, shows how to perfrom efficiently the first part. But, maybe I am wrong...
|
|
Yes , Dudidu's question was about the second part. But I think your approach ( I hope I understood it correctly ) does not fix the problem. Consider the case in which sqrt(n) sets are non-empty ( on the first level ). Traversing a non-empty set is of time complexity O(n) . Generating the permutation will have time complexity O(sqrt(n)*n).
My approach sorts the numbers using only the first 2 digits ( in base n ) as a key. This is done O(n) using bucket sort. The number formed by the first 2 digits in base n is actually the bin index so all numbers that belong to the same bin will have consecutive positions in the sorted array so the second part can also be performed efficiently. This is very similar to the initial solution proposed by towr. The only difference is that only 2 digits ( as opposed to the entire number ) need to be used as a key. With this restriction sorting can be done in O(n) time .
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Finding a Permutation
« Reply #15 on: Oct 31st, 2003, 11:15am » |
Quote Modify
|
Quote:| Divide all the bins into n sets, n bins in each... |
|
Barukh hi  ,
The problem with this approch is that in the worst case scenario it might occur that each of the n numbers will be "transfered" to a different set (i.e. there will be a single number in each set). Thus, there won't be any empty set and we return to first base  (i.e. we have to find the where the numbers are placed in a range of n2 optional bins).
Sorry...
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Finding a Permutation
« Reply #16 on: Oct 31st, 2003, 11:17am » |
Quote Modify
|
Quote:| What we need is to sort the numbers based on their first 2 digits (in base n)... |
|
DH Bravo !!!
This is correct (and you have succeeded to face the challenge) !
When I saw your answer at the first time I wasn't sure its correct (apparently since I thought of another answer) but after exaiming it deeply, I think it is exquisit!
Quote:| This is done O(n) using bucket sort... |
|
DH, sorting according to a part of the item's key is called Radix sort (and not bucket sort) --> look at the following link (if you're intrested) http://www.nist.gov/dads/HTML/radixsort.html.
|
|
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Finding a Permutation
« Reply #17 on: Oct 31st, 2003, 12:49pm » |
Quote Modify
|
on Oct 31st, 2003, 11:17am, Dudidu wrote:
Yeap , you are right the algorithm is called radix sort . Thanks for clearing this up !
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding a Permutation
« Reply #18 on: Oct 31st, 2003, 11:36pm » |
Quote Modify
|
on Oct 31st, 2003, 11:15am, Dudidu wrote:The problem with this approch is that in the worst case scenario it might occur that each of the n numbers will be "transfered" to a different set (i.e. there will be a single number in each set). Thus, there won't be any empty set and we return to first base (i.e. we have to find the where the numbers are placed in a range of n2 optional bins).
Sorry... |
|
I was not precise when explaning my approach. I didn't mean to represent sets and bins as nxn matrix. Rather, there is an array (sets) of linked lists (bins). So, if evey element goes to a different set, then each set contains just one bin, so the complexity is O(n).
After reading DH's and Dudidu's last posts, I have to admit that the radixsort approach is much cleaner.
|
|
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Finding a Permutation
« Reply #19 on: Nov 1st, 2003, 12:37am » |
Quote Modify
|
on Oct 31st, 2003, 11:36pm, Barukh wrote:
I was not precise when explaning my approach. I didn't mean to represent sets and bins as nxn matrix. Rather, there is an array (sets) of linked lists (bins). So, if evey element goes to a different set, then each set contains just one bin, so the complexity is O(n).
|
|
Hi Barukh,
That approach raises another problem because the linked lists must be sorted.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding a Permutation
« Reply #20 on: Nov 1st, 2003, 4:11am » |
Quote Modify
|
DH, you are right... I overlooked this. Thanks for clarifying things.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Finding a Permutation
« Reply #21 on: Nov 2nd, 2003, 12:10am » |
Quote Modify
|
Barukh hi,
I hope you didn't stop trying to solve the "follower" !!!
The solution that you provided is still not complete (as DH indicated) but it can be completed easily (and wisely (of course )).
The way that you chose to deal with the "follower" is very similar to solution that I thought about (e.g. the solution that was mentioned as the "another answer" in previous posts). So, keep on trying (I'm looking for the complete solution... )
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding a Permutation
« Reply #22 on: Nov 2nd, 2003, 9:53am » |
Quote Modify
|
Wow, Dudido, what's an inspiration! After failing to resolve "the minor problem" I thought this approach is ill.
But now! I will try to revive it, although it will not be easy having the radix sort solution in mind...
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Finding a Permutation
« Reply #23 on: Nov 2nd, 2003, 9:57am » |
Quote Modify
|
on Nov 2nd, 2003, 9:53am, Barukh wrote:Wow, Dudido, what's an inspiration! After failing to resolve "the minor problem" I thought this approach is ill.
But now! I will try to revive it, although it will not be easy having the radix sort solution in mind... |
|
Barukh , Good luck !!!
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Finding a Permutation
« Reply #24 on: Nov 5th, 2003, 9:32am » |
Quote Modify
|
on Nov 2nd, 2003, 9:57am, Dudidu wrote:
Barukh , Good luck !!! |
|
Dudidu, I must admit that I cannot find anything that doesn't resemble the radix sort solution in some way. If you've got something entirely different, please let (at least) me know.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print