wu :: forums - Print Page


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

        riddles >> cs >> aasp(another array sorting problem)
        
(Message started by: baskin on Apr 20^th, 2006, 5:45am)

Title: aasp(another array sorting problem)
Post by baskin on Apr 20^th, 2006, 5:45am

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.

Title: Re: aasp(another array sorting problem)
Post by inexorable on Apr 21^st, 2006, 11:56pm

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? ;)