lexicographical Smallest permutation in matrix with restricted exchange

Question

Following question was asked in Facebook Job interview aptitude test:

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 <= 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.

What I did?

I generated all the permutations First.

Then, I discarded those permutations that are not feasible. In Example 1: 1 3 3 is not feasible as position 1 and 2 is nonexchangeable.

From all the permissible permutation lists, i picked the lexicographical smallest one as the solution.

Problem with above solution:

My solution works perfectly for K<=25. When the size of K becomes greater than 25, the solution is really slow. For K=100, I did n't get the output even in 60 minutes.

My Questions here are:

How Should I optimize my solution?

Can it be done without generating all permutations?

Better Solution with Explanations and Pseudo-Code(or Code) will be highly helpful.

Thank you!

Answer 1

My solution works perfectly for K<=25. When the size of K becomes greater than 25, the solution is really slow.

Your solution will work very slow. As you are generating all permutations, so overall complexity for generating permutations is:

O(2^K).

Hence, O(2^K) will take a year as K can be as large as 100.

Can it be done without generating all permutations?

Yes, it can be done without generating all permutations.

How Should I optimize my solution?

You can solve this problem in linear time using(DFS and Connected Component) concept in graph theory.

Please note we will take second example for explaining the steps (involved in the algorithm) which I am going to descibe.

Step 1: Construct a graph G with K-1 Vertices. Thus V={0,1,2}

Step 2: Let an edge e connect two vertices whenever swapping the elements at those two positions is permissible. Therefore the edges are: E={(0,1) , (1,0) , (1,2) , (2,1)}

Step 3: Find all the Connected Components(CC) of this graph G(V,E). In example 2:

All the CC are:

CC1: {0, 1, 2}

Step 4: For each of the connected components, sort the elements available within that connected component in such a way that smallest index within the connected component gets smallest element, second smallest index gets second smallest element, etc.

In example 2:

Smallest index in CC1 = 0
Smallest index in CC1 = 1
Smallest index in CC1 = 2

• Smallest index 0 in CC1 gets the smallest element. Smallest element=1.

• Second smaller index in CC1 gets the second smallest element. Second smallest index =2.

• Third smaller index in CC1 gets the Third smallest element. Third smallest index =3.

Thus, The result after sorting CC1 as per above rule is (1,2,3).

When Step 4 is done for all connected components, we have the lowest possible permutation.

Therefore, 1 2 3 is the lexicographically smallest permutation in example 2.

Pseudo-Code(or Code) will be highly helpful.

As I had already described the logic, here is the Code in C++:

vector<int>TMP_IP;
char Adjacency[LIMIT][LIMIT];
vector<vector<int> >ADJ_vector(LIMIT);
int MARKED[LIMIT];
vector<int>connected_COMPONENTS;
vector<int>Positions_vector;
void DepthFirstTraversal(int u)
{
     MARKED[u]=1;
     connected_COMPONENTS.push_back(u);
     for(int j=0;j<ADJ_vector[u].size();++j)
          if(!MARKED[ADJ_vector[u][j]] )
             DepthFirstTraversal(ADJ_vector[u][j]);
}
//Print result
void lexo_smallest(int K)
{
     for(int i=0;i<K;++i)
                  cout<<TMP_IP[i]<<" ";
             cout<<endl;
}
int main()
{
    int K,ip;
    string rows[109];
    scanf("%d",&K);
    for(int i=0;i<K;++i)
    {
            scanf("%d",&ip);
            TMP_IP.push_back(ip);
    }

    for(int i=0;i<K;++i)
               cin>>rows[i];


    for(int i=0;i<K;++i)
         for(int j=0;j<rows[i].size();++j)
             Adjacency[i][j]=rows[i][j];


    for(int i=0;i<K;++i)
    for(int j=0;j<K;++j)
     if(Adjacency[i][j]=='Y')
         ADJ_vector[i].push_back(j);  

            for( int i = 0 ; i <K ; ++i )
            {   
                if( !MARKED[ i ] )
                { 

                    DepthFirstTraversal( i ); 
                    for(int x=0;x<connected_COMPONENTS.size();++x)
                    {
                            Positions_vector.push_back(TMP_IP[connected_COMPONENTS[x]]);
                    }
                    sort(connected_COMPONENTS.begin(),connected_COMPONENTS.end());
                    sort(Positions_vector.begin(),Positions_vector.end());
                    for(int x=0;x<connected_COMPONENTS.size();++x)
                    {
                            TMP_IP[connected_COMPONENTS[x]]=Positions_vector[x];
                    }
                    connected_COMPONENTS.clear();
                    Positions_vector.clear();

                }
            }
            lexo_smallest(K);

    return 0;
}

DEMO @ IDEONE

Complexity of the above solution:

The total time for taking input is O(K^2).

Complexity of above algorithm is same as DFS. O(V+E).

Overall time: O(K^2)+O(V+E)

Even for K=5000, the above solution is amazingly fast.