|
||||
|
Title: Another Permutation Question... Post by Dudidu on Nov 13th, 2003, 6:19am A permutation swap is a pair ([pi](i), [pi](j)) such that (i < j) and ([pi](i) > [pi](j))1. 1) For "warm up": What is the maximal number of swaps that a permutation of size n (e.g. [n]) has ? 2) Devise an algorithm that determines the number of swaps in a given permutation of size n. 1Notice: a single element that is "out of place" may cause a number of swaps. |
||||
|
Title: Re: Another Permutation Question... Post by towr on Nov 13th, 2003, 7:57am Could you give a bit more background? Because I don't really understand what is asked.. |
||||
|
Title: Re: Another Permutation Question... Post by visitor on Nov 13th, 2003, 8:23am I think he's saying you have an array of unsorted elements, and you sort it by swapping any two elements (not necessarily adjacent). Instead of trying to sort it as quickly as possible, you want to maximize the number of swaps before it becomes completely sorted and no more swapping is possible. My first thought was that the maximum is when the original permutation is sorted in decreasing order and you only swap adjacent numbers to move each element as slowly as possible to its final position. Every swap would move two numbers one step closer, so the answer would be something like n(n-1)/2. But maybe you could increase that by doing partial sorts and then swapping the end numbers by several positions to unsort what was sorted. |
||||
|
Title: Re: Another Permutation Question... Post by Dudidu on Nov 13th, 2003, 8:27am on 11/13/03 at 07:57:58, towr wrote:
a permutation [pi] of size n (noted as [n]) is a one-to-one function from {1,2,...,n}[smiley=onetoone.gif]{1,2,...,n}. For example, if [pi](1) = 2, [pi](2) = 3 and [pi](3) = 1 then if [pi] is applied to the 3-tuple (1,2,3) we will get (2,3,1). In my previous thread I defined a permutation swap. I will use my previous example as an example to understand what is a swap. In this example there are 2 swaps (e.g. (2,1), (3,1)) since (1 < 3) but (2 = [pi](1) > [pi](3) = 1) and (2 < 3) but (3 = [pi](2) > [pi](3) = 1). Now it's your turn to start answering... :P P.S. hope this helps (if the answer is no, don't hesitate to ask more)... |
||||
|
Title: Re: Another Permutation Question... Post by Barukh on Nov 13th, 2003, 11:16am Let's see if I understood correctly. "warm up": [smiley=blacksquare.gif] [hide]nC2 = n(n-1)/2 swaps, achieved by the permutation [pi](i) = n+1-i (as Visitor already pointed).[/hide] [smiley=blacksquare.gif] Also, let me guess that you want a linear time complexity for the second part? |
||||
|
Title: Re: Another Permutation Question... Post by Dudidu on Nov 15th, 2003, 11:09am Barukh hi, Your solution to the "warm up" question is correct ;D. Indeed, the reverse sorted permutation [pi]: (1, 2, ..., n) [smiley=onetoone.gif] (n, n-1, ..., 1) has the maximal number of swaps. Quote:
1 As I know, the answer whether swaps counting can be performed more efficiently, or if there exists a [smiley=comega.gif](n log n) lower bound, remains an open question :P. |
||||
|
Title: Re: Another Permutation Question... Post by william wu on Nov 15th, 2003, 7:26pm on 11/13/03 at 06:19:32, Dudidu wrote:
Some side information: These are also called "backward pairs". If the number of backward pairs in a permutation is even, we call that an "even permutation"; similarly, if the number of backward pairs is odd, we call that an "odd permutation". These ideas are associated with some neat group theory, and can be used to resolve various puzzles, such as Sam Lloyd's 15-14 sliding puzzle. |
||||
|
Title: Re: Another Permutation Question... Post by Barukh on Nov 20th, 2003, 6:13am The following beautiful solution was proposed by a friend of mine (I wish it was my…) [smiley=blacksquare.gif] [hide]The idea of the algorithm is to divide the permutation [pi] into 2 halves and count how many swaps are between elements in different halves; then, repeat the process recursively for every half. Here’s the way to do it efficiently on the first level: maintain two variables c and B, both set to 0 at the beginning. Now, for every i, if [pi](i) > n/2, then set c = c+1; if [pi](i) [le] n/2, then set B = B+c. At the end of this algorithm, B will contain the number of swaps ([pi](i) > n/2, [pi](j) [le] n/2). To extend this efficiently to recursive levels, here’s another key idea: Assume n is a power of 2, and divide the permutation into 2k equal intervals. Then, k-1 MSBs in binary representation of [pi](i) – 1 is the number of the interval [pi](i) belongs to. Performing the aforementioned algorithm at the k-th bit on every interval gives the number of swaps ([pi](i), [pi](j)), where [pi](i), [pi](j) are in different halves of the interval. This may be done in linear time maintaining 2k counters c0, …, c2^k-1. Because the number of levels is log(n), the overall complexity of the algorithm is O(nlog(n)), as required. To make it more clear, here’s a specific example. Let n=8, and [pi] = (5 2 8 7 6 4 3 1). The attached table shows all 3 levels of the algorithm in detail.[/hide] [smiley=blacksquare.gif] As usual, an excellent puzzle from Dudidu’s pool. |
||||
|
Title: Re: Another Permutation Question... Post by Dudidu on Nov 20th, 2003, 8:18am Barukh hi, I will need some assistance in order to understand your solution (I didn't understand the attached table) ???: Quote:
Quote:
Thanks... |
||||
|
Title: Re: Another Permutation Question... Post by James Fingas on Nov 20th, 2003, 10:04am Dudidu, I was able to come up with the same solution. Here's an example of how it works: 1 8 4 3 2 9 6 7 5 The median value is 5, so we replace the numbers with H and L (Higher than 5 and Lower than 5), assigning 5=L arbitrarily: L H L L L H H H L c 0 1 1 1 1 2 3 4 4 B 0 0 1 2 3 3 3 3 7 c is just keeping count of the number of Hs less before the current position, and B adds that number of swaps when we see an L. We then separate out the Ls and Hs and count separately for the two sublists: the high list is 8, 9, 6, 7, and the low list is 1, 4, 3, 2, 5. |
||||
|
Title: Re: Another Permutation Question... Post by Dudidu on Nov 25th, 2003, 9:45am Barukh and James hi, I read your solution (Barukh) and your explanation (James) and you (both) are right! Bravo! ;D I must admit that the "merge technique" is beautifully done. Two remarks: 1) Like (almost) anything in CS there is more then one solution for this problem (although the general ideas are similar) - i.e. another solution uses (intresting) data structures that help to count easily the number of swaps (If you're intrested, you can think of it as a "follower" (and if you're not, I will post it later...)). 2) I have a very similar divide-and-conquer solution that I'll post later (no time :-/), which (I think) simplifies this solution a little bit, and is more intuitive (for my opinion). Cheers... |
||||
|
Title: Re: Another Permutation Question... Post by Dudidu on Nov 27th, 2003, 4:26am on 11/25/03 at 09:45:11, Dudidu wrote:
In order to count the number of swaps, we only need to modify merge sort (http://www.nist.gov/dads/HTML/mergesort.html) so that it counts inversions as it sorts. Practically speaking, if we split an array into two halves [ ...L... | ...R... ] then every swap will be either a left swap (involves two elements from L), a right swap (involves two elements from R) or a crossover swap (involves one element from L and one element from R). Practically, the only task is to count the crossover swaps (since the other two kinds will be inductivally solved by the recursive calls). It should be noticed that these swaps (i.e. crossover) are not affected when L and R are sorted, so we will count them during the merge of the sorted L and R. This is done as follows. Every time we add an element from L to the "merged List", we count the number of elements of R with which it forms a swap - if we're comparing the ith element of L to the jth element of R, and that L[i] < R[j] (thus, L[i] is the next element in the "merged list") then L[i] will be in a swap with each of the elements in R[1 ... j-1] (adding (j - 1) swaps)... It should be noted that this extra counting doesn't affect the asymptotic running time of merge sort which is O(nlogn). [/hide] Quote:
|
||||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |