Author |
Topic: Another Permutation Question... (Read 1912 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Another Permutation Question...
« on: Nov 13th, 2003, 6:19am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Another Permutation Question...
« Reply #1 on: Nov 13th, 2003, 7:57am » |
Quote Modify
|
Could you give a bit more background? Because I don't really understand what is asked..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
visitor
Guest
|
|
Re: Another Permutation Question...
« Reply #2 on: Nov 13th, 2003, 8:23am » |
Quote Modify
 Remove
|
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.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Another Permutation Question...
« Reply #3 on: Nov 13th, 2003, 8:27am » |
Quote Modify
|
on Nov 13th, 2003, 7:57am, towr wrote:| Could you give a bit more background? Because I don't really understand what is asked.. |
|
Sure,
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.S. hope this helps (if the answer is no, don't hesitate to ask more)...
|
| « Last Edit: Nov 13th, 2003, 8:30am by Dudidu » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Another Permutation Question...
« Reply #4 on: Nov 13th, 2003, 11:16am » |
Quote Modify
|
Let's see if I understood correctly. "warm up":
[smiley=blacksquare.gif]
nC2 = n(n-1)/2 swaps, achieved by the permutation [pi](i) = n+1-i (as Visitor already pointed).
[smiley=blacksquare.gif]
Also, let me guess that you want a linear time complexity for the second part?
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Another Permutation Question...
« Reply #5 on: Nov 15th, 2003, 11:09am » |
Quote Modify
|
Barukh hi,
Your solution to the "warm up" question is correct  . Indeed, the reverse sorted permutation [pi]: (1, 2, ..., n) [smiley=onetoone.gif] (n, n-1, ..., 1) has the maximal number of swaps.
Quote:| Also, let me guess that you want a linear time complexity for the second part? |
|
I was hoping to an O(n log(n)) time complexity algorithm (but if you get a linear time algorithm, I will be more then thrilled1 to hear about it)
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 .
|
| « Last Edit: Nov 19th, 2003, 12:52am by Dudidu » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Another Permutation Question...
« Reply #6 on: Nov 15th, 2003, 7:26pm » |
Quote Modify
|
on Nov 13th, 2003, 6:19am, Dudidu wrote:A permutation swap is a pair ([pi](i), [pi](j)) such that (i < j) and ([pi](i) > [pi](j))1.
|
|
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.
|
| « Last Edit: Nov 15th, 2003, 7:54pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
The following beautiful solution was proposed by a friend of mine (I wish it was my…)
[smiley=blacksquare.gif]
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.
[smiley=blacksquare.gif]
As usual, an excellent puzzle from Dudidu’s pool.
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Another Permutation Question...
« Reply #8 on: Nov 20th, 2003, 8:18am » |
Quote Modify
|
Barukh hi,
I will need some assistance in order to understand your solution (I didn't understand the attached table)  :
Quote:| divide the permutation into 2 halves and count how many swaps are between elements in different halves... |
|
This "divide and conquer" strategy correlates with one of the solutions I have in mind. However,
Quote:| 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). |
|
I do not understand this "combining" technique (for example I don't understand how do you pass on all the i's...) - So... can you explain it (again ).
Thanks...
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Another Permutation Question...
« Reply #9 on: Nov 20th, 2003, 10:04am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 20th, 2003, 10:07am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Another Permutation Question...
« Reply #10 on: Nov 25th, 2003, 9:45am » |
Quote Modify
|
Barukh and James hi,
I read your solution (Barukh) and your explanation (James) and you (both) are right! Bravo!
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...
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Another Permutation Question...
« Reply #11 on: Nov 27th, 2003, 4:26am » |
Quote Modify
|
on Nov 25th, 2003, 9:45am, Dudidu wrote:| 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)... |
|
As I promised...
In order to count the number of swaps, we only need to modify merge sort 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).
Quote:| ...another solution uses (intresting) data structures that help to count easily the number of swaps... |
|
If nobody is intrested I'll post it soon (and if someone is interested, please inform me).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Another_Permutation_Example.zip