algorithm - 矩阵中具有受限交换的字典序最小排列

Question

在 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 也没有得到输出.

我的问题是:

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

不生成所有排列是否可以做到？

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

谢谢!

Answer 1

我的解决方案非常适用于 K<=25。当 K 的大小变得大于 25 时，解决方案真的很慢。

您的解决方案运行速度会很慢。当您生成所有排列时，生成排列的总体复杂度为:

O(2^K)。

因此，O(2^K) 需要一年时间，因为 K 可以大到 100。

不生成所有排列是否可以做到？

是的，它可以在不生成所有排列的情况下完成。

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

您可以使用图论中的( DFS 和 Connected Component )概念在线性时间内解决这个问题。

请注意，我们将以第二个示例来解释我将要描述的步骤(涉及算法)。

第 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 中:

所有抄送都是:

CC1: {0, 1, 2}

第 4 步:对于每个连接组件，对该连接组件内可用的元素进行排序，这样连接组件内的最小索引获得最小元素，第二小的索引获得第二小的索引元素等

在示例 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;
}

DEMO @ IDEONE

上述解决方案的复杂性:

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

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

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

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