title: lexicographical Smallest permutation in matrix with restricted exchange
body: <p>Following question was asked in <strong>Facebook</strong> Job interview <strong>aptitude test</strong>:</p>
  
  <pre><code>A permutation is a list of K numbers, each between 1 and K (both inclusive),
  that has no duplicate elements.
  
  Permutation X is lexicographically smaller than Permutation Y iff for some
  i &lt;= K:
  
  All of the first i-1 elements of X are equal to first i-1 elements of Y.
  ith element of X is smaller than ith element of Y.
  You are given a permutation P, you can exchange some of its elements as many 
  times as you want in any order. You have to find the lexicographically smallest     
  Permutation that you can obtain from P.
  
  K is less than 101.
  
  Input Format:
  First line of input contains K being the size of permutation.
  Next line contains K single spaced numbers indicating the permutation.
  Each of next K lines contains K characters, character j of line i is equal to
  'Y' if you can exchange ith and jth element of a permutation, and 
  'N' otherwise.
  
  Output Format:
  Print K numbers with a space separating each of them indicating the 
  permutation.
  
  Sample Input
  3
  3 1 2
  NNY
  NNN
  YNN
  
  Sample Output
  2 1 3
  Sample Input 
  3
  3 2 1
  NYN
  YNY
  NYN
  
  Sample Output
  
  1 2 3 
  
  In the first example you can exchange first element with last element to
  obtain 2 1 3 from 3 1 2.
  </code></pre>
  
  <p><strong>What I did?</strong></p>
  
  <p>I generated all the permutations First.</p>
  
  <p>Then, I discarded those permutations that are not feasible.
  In Example 1: <code>1 3 3</code> is not feasible as position 1 and 2 is nonexchangeable.</p>
  
  <p>From all the permissible permutation lists, i picked the lexicographical smallest one as the solution.</p>
  
  <p><strong>Problem with above solution</strong>:</p>
  
  <p>My solution works perfectly for <code>K&lt;=25</code>. When the size of K becomes greater than 25, the solution is really slow. For <code>K=100</code>, I did n't get the output even in <code>60 minutes</code>.</p>
  
  <p>My Questions here are:</p>
  
  <p><strong>How Should I optimize my solution?</strong></p>
  
  <p><strong>Can it be done without generating all permutations?</strong></p>
  
  <p>Better Solution with Explanations and  Pseudo-Code(or Code) will be highly helpful.</p>
  
  <p>Thank you!</p>