wu :: forums - Print Page


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

        riddles >> cs >> Finding a Permutation
        
(Message started by: Dudidu on Oct 29^th, 2003, 6:05am)

Title: Finding a Permutation
Post by Dudidu on Oct 29^th, 2003, 6:05am

Given n real numbers x₁,...,x_n where each x_i[in][0,1], devise an algorithm that will output a permutation of them ([sigma]) such that [sum]_i=2ⁿ |x[smiley=subsigma.gif]_(i) - x[smiley=subsigma.gif]_(i-1)| [le] 2.

Hint:[hide] An algorithm that sorts x₁,...,x_n is not efficent enough.[/hide]

Title: Re: Finding a Permutation
Post by towr on Oct 29^th, 2003, 7:39am

::[hide]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 :P
But you probably want O(n) (or better), instead of O(n log(n)) with a better constant[/hide]::

Title: Re: Finding a Permutation
Post by Dudidu on Oct 30^th, 2003, 12:13am

towr,
when I said in my hint that [hide] "an algorithm that sorts ... is not efficent enough" [/hide] I didn't mean to say that it doesn't solve the problem. I meant to indicate that [hide]O(nlogn)[/hide] 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 :-/.

Title: Re: Finding a Permutation
Post by towr on Oct 30^th, 2003, 1:31am

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..

Title: Re: Finding a Permutation
Post by Dudidu on Oct 30^th, 2003, 3:08am

on 10/30/03 at 01:31:02, towr wrote:

I was just wondering how much more efficient you wanted..

I'm looking for a [hide]O(n) time complexity algorithm[/hide].
Hope this helps... ;)

Title: Re: Finding a Permutation
Post by DH on Oct 30^th, 2003, 6:18am

::
[hide]
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.

[/hide]

Title: Re: Finding a Permutation
Post by towr on Oct 30^th, 2003, 7:45am

I wish I had thought of that..

Title: Re: Finding a Permutation
Post by Dudidu on Oct 30^th, 2003, 9:43am

Well done DH !!!
A correct solution ;D !
but can you solve the "follower"...

Title: Re: Finding a Permutation
Post by Barukh on Oct 30^th, 2003, 9:49am

I would like to join Dudidu in praising DH's solution. As for the follower:
[smiley=blacksquare.gif]
[hide]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 = n².[/hide]
[smiley=blacksquare.gif]
And the last but not the least: thanks, Dudidu, for this brilliant puzzle!

Title: Re: Finding a Permutation
Post by Dudidu on Oct 30^th, 2003, 10:00am

Barukh,
Your solution for the follower is a little bit problematic:

[hide]If you take K = n², you have (of course) n² bins. Thus, when you want to "build" your permutation you will need to look in all the bins, and this can take O(n²) time complexity.[/hide]

So, how can you deal with this minor (::)) problem?

Title: Re: Finding a Permutation
Post by towr on Oct 30^th, 2003, 10:22am

::[hide]hash it :P[/hide]::

Title: Re: Finding a Permutation
Post by Barukh on Oct 30^th, 2003, 10:50am

I didn't have time to answer (seems the posts are coming with a speed of light ;D).

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][hide]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).[/hide][smiley=blacksquare.gif]

Does it make sense?

Title: Re: Finding a Permutation
Post by DH on Oct 30^th, 2003, 3:04pm

on 10/30/03 at 10:50:29, Barukh 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) .

But I think the following works:
[hide]
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.
[/hide]

Title: Re: Finding a Permutation
Post by Barukh on Oct 31^st, 2003, 12:36am

on 10/30/03 at 15:04:33, 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 n² bins, we cannot just organize them as an array, since then traversing it will take O(n²) 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...

Title: Re: Finding a Permutation
Post by DH on Oct 31^st, 2003, 2:14am

Quote:

....
I think Dudidu's question was about the second part: because there are n² bins, we cannot just organize them as an array, since then traversing it will take O(n²) 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 [hide] 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 [/hide].

Title: Re: Finding a Permutation
Post by Dudidu on Oct 31^st, 2003, 11:15am

Quote:

Divide all the bins into n sets, n bins in each...

Barukh hi :D,
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 n² optional bins).
Sorry...

Title: Re: Finding a Permutation
Post by Dudidu on Oct 31^st, 2003, 11:17am

Quote:

What we need is to sort the numbers based on their first 2 digits (in base n)...

DH Bravo ;D!!!
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.

Title: Re: Finding a Permutation
Post by DH on Oct 31^st, 2003, 12:49pm

on 10/31/03 at 11:17:08, Dudidu wrote:

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.

Yeap , you are right the algorithm is called radix sort . Thanks for clearing this up !

Title: Re: Finding a Permutation
Post by Barukh on Oct 31^st, 2003, 11:36pm

on 10/31/03 at 11:15:01, 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 n² 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.

Title: Re: Finding a Permutation
Post by DH on Nov 1^st, 2003, 12:37am

on 10/31/03 at 23:36:31, Barukh wrote:

Hi Barukh,

That approach raises another problem because the linked lists must be sorted.

Title: Re: Finding a Permutation
Post by Barukh on Nov 1^st, 2003, 4:11am

DH, you are right... I overlooked this. Thanks for clarifying things. ::)

Title: Re: Finding a Permutation
Post by Dudidu on Nov 2^nd, 2003, 12:10am

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... ;D)

Title: Re: Finding a Permutation
Post by Barukh on Nov 2^nd, 2003, 9:53am

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...

Title: Re: Finding a Permutation
Post by Dudidu on Nov 2^nd, 2003, 9:57am

on 11/02/03 at 09:53:00, 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 !!!

Title: Re: Finding a Permutation
Post by Barukh on Nov 5^th, 2003, 9:32am

on 11/02/03 at 09:57:16, 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.

Title: Re: Finding a Permutation
Post by Dudidu on Nov 5^th, 2003, 10:25am

Barukh, let me help you a little ;).
Lets recap what we have on the 2^nd question (e.g. the "follower"):
[hide]As you suggested, we divided the set of numbers into n² bins. Every time that we have "transfered" a number into bin_i, 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, ..., n²-1}.
[/hide] So...
Barukh, now it's your turn to complete the algorithm.

Title: Re: Finding a Permutation
Post by Barukh on Nov 6^th, 2003, 2:22am

on 11/05/03 at 10:25:48, Dudidu wrote:

[hide]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, ..., n²-1}.[/hide]

Yes, I got it. And what is most obvious way to do it (at least for me)? Radix sort! ;D

Title: Re: Finding a Permutation
Post by Dudidu on Nov 6^th, 2003, 3:22am

on 11/06/03 at 02:22:15, Barukh wrote:

Yes, I got it. And what is most obvious way to do it (at least for me)? Radix sort! ;D

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" ;)).

Title: Re: Finding a Permutation
Post by DH on Nov 6^th, 2003, 5:39am

on 11/06/03 at 03:22:50, Dudidu wrote:

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" ;)).

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.

Title: Re: Finding a Permutation
Post by Dudidu on Nov 6^th, 2003, 6:06am

on 11/06/03 at 05:39:46, 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...

Title: Re: Finding a Permutation
Post by Barukh on Nov 6^th, 2003, 11:20am

on 11/06/03 at 05:39:46, DH wrote:

Let's push the limit a little further :).

And let me push it further still ;D

Using the radix sort idea, it is possible in linear time to deliver a permutation with the sum of absolute differences [le] 1 + 1/n^k for every constant k.

An amazing problem!