//N=no of digit of n;
//ar[0]=10; for i=1,N a[i]=ith digit of n from left
i=N-1;
while(ar[i]<ar[i+1])i--;
if(i==0)return ;//i.e no answer
j = N;
while(ar[i]<ar[j])j--;
swap( ar[i],ar[j]);
j = N; i++;
while(i<=j)
{
swap(ar[i], ar[j]);
i++; j--;
}
print(ar);
i think this will work.. :)
On 2/28/06, ajay mishra <[EMAIL PROTECTED]> wrote:
> @milochen
> Your approach is not correct. I am giving a counter example
>
> say our input is
> 423, so by ur approach the solution is 243 or 234
> but the correct answer is 342.
>
> The approach given by dhyanesh and dazi is correct.
>
> On 2/28/06, milochen <[EMAIL PROTECTED]> wrote:
> >
> >
> > Does it always have the solution?
> > What about that 123456789 ?
> >
> > I think that it doesn't always have solution for all case.
> >
> > I am sorry that I couldn't give you a C++ code ,
> > since I have no complier,so I couldn't ensure whether
> > the code will be compile successful.
> >
> > Assume X=(x_1,x_2,x_3, ...,x_(n-2), x_(n-1), x_n) is
> > our instance s.t. Y=(y_1,y_2,y_3,...,y_(n-2), y_(n-1),y_n)
> > is the solution for X.
> > from n-1 to 1, we suppose i is the first i s.t. x_i > x_(i+1)
> >
> > then the solution is almost like the followng
> > Y
> > =(y_1,y_2,y_3,...,y_(n-2), y_(n-1),y_n)
> > =
> > (x_1,x_2,x_3,...,x_(i-3),x_(i-2),
> > x_(i-1),x_(i+1),x_i, x_(i+2),x_(i+3)...
> > ...x_(n-2),x_(n-1),x_n )
> >
> > To pay attension for that
> > we just need to do one time swap to get
> > the solution.
> >
> > From n-1 to 1, If you cannot find the
> > first i s.t. x_i > x_(i+1), then the instance X
> > have no solution.
> >
> >
> >
> >
>
>
> --
> Ajay kr. Mishra
> http://ajay.mishra19.googlepages.com
> IIT KGP
>
>
>
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
