a very interesting problem

if you see O(n). dont hesitate just do linear traversal

http://www.careercup.com/question?id=14912744


void PrintReverse(int i,int j)
{
for(int k=j;k>=i;k--)
cout<<k<<endl;
}

void WritePermu(string signature)
{
int N=signature.length();
int lasti=1;
for(int i=0;i<N;i++)
{
if(signature[i]=='I')
{
PrintReverse(lasti,i+1);
lasti=i+2;
}
}
PrintReverse(lasti,N+1);
}

it can also be solved using topological sort