Author |
Topic: aasp(another array sorting problem) (Read 909 times) |
|
baskin
Newbie
Gender: 
Posts: 26
|
 |
aasp(another array sorting problem)
« on: Apr 20th, 2006, 5:45am » |
 Quote  Modify
|
An array of size N has distinct values 1…N in random order. You have only operator called rev(X) (where X is any value from 0 to N-1) which reverses all values from 0 to X (example values 2,3,1,4 and rev(2) gets you 1,3,2,4). Our objective is to sort the array using minimum number of Rev(X) functions. How many permutations of N size array require exactly N number of rev(X) operators to get sorted.. for size 3 only 1,3,2 requires moves.
|
|
 IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: aasp(another array sorting problem)
« Reply #1 on: Apr 21st, 2006, 11:56pm » |
Quote Modify
|
I got a recurrence relation to solve this .
if P(N,K) is the number of permutations of length N which require minimum of K reverses then
P(N,K)=P(N-1,K-1)(N-2) + P(N-1,K-1) +P(N-1,K)
where base conditions would be
P(1,0)=1
P(1,1)=0
if 0>=N or 0>K then P(N,K)=0
substituting K=N we get the required answer for above problem
A naive program for finding P(N,K) wud be as follows
int perm(int n, int k)
{
if((n<=0)||(k<0))
return 0;
if((n==1)&&(k==0))
return 1;
if((n==1)&&(n==1))
return 0;
return (perm(n-1,k-2)*(n-2)+perm(n-1,k-1)+perm(n-1,k));
}
How about generating optimally all the P(N,K) permutations which require K reverses? 
|
| « Last Edit: Apr 21st, 2006, 11:58pm by inexorable » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print