查找某些字符串的字典序最小排列

Question

标题似乎是一个很常见的问题，但请耐心等待。

基本上可以说在字符串的每个索引处你知道哪些字母表可能在该索引中，然后你想找到字典上最小的排列。

例如：

Index  |  Options
-------|----------
  1    |  'b'
  2    |  'c', 'a'
  3    |  'd', 'c'
  4    |  'c', 'a'

因此，o/p 应该是 badc。是的，顺便说一句，字符不能重复，所以没有贪心算法。

我认为我们可以通过创建 queue 或字符串的某些内容来使用某种广度优先搜索，每次我们发现我们无法创建另一个排列时，您将其从列表中弹出。怀疑这是最佳的，但一定是 O(N) 中的东西。有什么想法吗？

不，我不认为 C 语言不好，但我更喜欢 C/C++ 中的代码片段：p

谢谢！

Answer 1

天真的方法是使用回溯并尝试所有可能的解决方案，但是它不够有效（26！）。然后，您可以在位掩码的帮助下使用动态编程来改进此回溯解决方案。位掩码可以帮助您存储到目前为止使用过的字符。

编写一个递归函数，它接受两个输入，一个是应该分配一个字符的索引，一个是指示我们到目前为止使用了哪些字符的位掩码。最初位掩码包含 26 个零，这意味着我们没有使用任何字符。将字符分配给某个索引后，我们相应地更改位掩码。例如，如果我们使用字符 a，我们将位掩码的第一位设置为 1。这样您就不会解决很多重叠的子问题。

#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;

vector<vector<char> > data;
map< pair<int,int>, string > dp;

string func( int index, int bitmask ){
    pair<int,int> p = make_pair(index,bitmask);
    if ( dp.count( p ) )
        return dp[p];
    string min_str = "";
    for ( int i=0; i<data[index].size(); ++i ){
        if ( (bitmask&(1<<(data[index][i]-'a'))) == 0 ){
            string cur_str = "";
            cur_str += data[index][i];
            if ( index+1 != data.size() ){
                int mask = bitmask;
                mask |= 1<<(data[index][i]-'a');
                string sub = func(index+1, mask);
                if (sub == "")
                    continue;    
                cur_str += sub;
            }
            if ( min_str == "" || cur_str < min_str ){
                min_str = cur_str;
            }
        }
    }
    dp[p] = min_str;
    return min_str;
}


int main()
{
    data.resize(4);
    data[0].push_back('b');
    data[1].push_back('c');
    data[1].push_back('a');
    data[2].push_back('d');
    data[2].push_back('c');
    data[3].push_back('c');
    data[3].push_back('a');
    cout << func(0,0) << endl;
}

Answer 2

这个可以通过匹配算法来解决。您可以使用网络流解决方案来解决此问题。这可以分解为二分图问题。

准确的说是最大权重分配问题或者最大成本最大匹配问题。

下面是二分顶点集 -

LEVEL          Alphabets
 1                 a  
 2                 b
 3                 c
 4                 d
                   e
                   .
                   .
                   .
                   z

现在仅当且仅当这些是该级别的选项时，才将集级别中的边分配给集字母表。所以这些将是这里的边缘 - {1,b} , {2,a}, {2,c} , {3,c} , {3,d} ,{4,a} ,{4,c} 现在，要获得按字典顺序排列的最少结果，您需要以这种方式为边缘分配权重 -

Edge Wt. = 26^(N-Level) * ('z' - Alphabet)

因此，例如边 {2,c} 的边权重将为

26^(4-2) * (26-3) =  26^2*23

现在您可以使用标准的最大成本最大匹配解决方案。这是一个多项式解。就我现在的想法而言，这将是最好的方法。朴素的解决方案是指数解决方案 26^N，因此我认为您会对多项式解决方案感到满意。

查找某些字符串的字典序最小排列

Finding Lexicographically smallest arrangement of some string

c++

algorithm

permutation

breadth-first-search