5

在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。

我的问题是：

我应该如何优化我的解决方案？

可以在不产生所有排列的情况下完成吗？

带有解释和伪代码（或代码）的更好解决方案将非常有帮助。

谢谢！

4

3 回答 3

4

我的解决方案非常适合 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;
}

演示@IDEONE

上述解决方案的复杂性：

接受输入的总时间是 O(K^2)。

上述算法的复杂度与 DFS 相同。O(V+E)。

总时间：O(K^2)+O(V+E)

即使对于 K=5000，上述解决方案也非常快。

于 2013-04-04T18:27:48.310 回答
0

在这种情况下，您首先需要形成一个新矩阵，其中 if a(i,j)is Ythen 这意味着jthposition 的元素可以到达ith place。

这项任务可以通过应用Floyd Warshall 算法轻松完成，通过将所有 Y 替换为 1 并将所有 N 替换为无穷大（或非常大的数字）。因此，在应用 Floyd Warshall 之后，如果任何元素a(i,j)小于infinity然后元素 atjth position可以放置在 position i。

现在任务很简单。贪婪地选择元素，即为每个元素i提供一个可以交换位置的元素列表。所以现在按顺序从位置 1 到 end 并且对于每个i，找到具有最小值（索引 j）的元素a(i,j)（Y即小于无穷大）并交换i和j。

于 2013-04-04T18:01:30.050 回答
0

您可以按位置进行操作。

对于最左边的位置，找到您能找到的最小数字并将其交换到位置 1。这可以通过检查从位置 1 到第一个位置的路径是否存在等等来完成。

于 2013-04-04T18:16:24.600 回答