以下问题在Facebook求职面试能力测试中被问到:
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.
我做了什么？
我首先生成了所有的排列.
然后,我放弃了那些不可行的排列.在示例1中:1 3 3由于位置1和2是不可更改的,因此是不可行的.
从所有允许的排列列表中,我选择了字典最小的排列作为解决方案.
以上解决方案的问题:
我的解决方案非常适合K<=25.当K的大小大于25时,解决方案非常慢.因为K=100,我甚至没有得到输出60 minutes.
我的问题是:
我该如何优化我的解决方案？
可以在不产生所有排列的情况下完成吗？
解释和伪代码(或代码)的更好解决方案将非常有用.
谢谢!
我的解决方案对于 K<=25 非常有效。当 K 的大小大于 25 时，求解速度非常慢。
您的解决方案运行速度会非常慢。当您生成所有排列时，生成排列的总体复杂性为：
O(2^K)。
因此，O(2^K) 将需要一年的时间，因为 K 可以大到 100。
可以在不生成所有排列的情况下完成吗？
是的，无需生成所有排列即可完成。
我应该如何优化我的解决方案？
您可以使用图论中的（ DFS和连通分量）概念在线性时间内解决这个问题。
请注意，我们将使用第二个示例来解释我将要描述的步骤（涉及算法）。
步骤 1 ：构造一个具有 K-1 个顶点的图 G。因此 V={0,1,2}
步骤 2 ：只要允许交换两个位置的元素，就让边e连接两个顶点。因此边是： E={(0,1) , (1,0) , (1,2) , (2,1)}
步骤3 ：找到该图G(V,E)的所有连通分量(CC) 。在示例 2 中：
所有的CC都是：
CC1: {0, 1, 2}
步骤 4：对于每个连接的组件，对该连接的组件中可用的元素进行排序smallest index within the connected component gets smallest element，使得第二小的索引获得第二小的元素，依此类推。
在示例 2中：
Smallest index in CC1 = 0
Smallest index in CC1 = 1
Smallest index in CC1 = 2
CC1 中最小的索引 0 获取最小元素。最小元素=1。
CC1 中第二个较小的索引获取第二小的元素。第二小的索引=2。
CC1 中第三个较小的索引获取第三小的元素。第三小的索引=3。
因此，CC1按照上述规则排序后的结果是(1,2,3)。
当对所有连接的组件完成第 4 步后，我们就得到了可能的最低排列。
因此，1 2 3是示例 2 中按字典顺序排列的最小排列。
伪代码（或代码）将非常有帮助。
正如我已经描述的逻辑，这里是 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;
}
上述解决方案的复杂度：
获取输入的总时间为 O(K^2)。
上述算法的复杂度与DFS相同。O(V+E)。
总时间：O(K^2)+O(V+E)
即使对于 K=5000，上述解决方案也快得惊人。