c++ - 查找某个字符串的字典顺序最小排列

Question

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

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

例如:

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

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

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

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

谢谢!

Answer 1

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

准确地说，最大权重分配问题或最大成本最大匹配问题将是一个解决方案。

下面是二分顶点集 -

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，所以我认为您会对多项式解决方案感到满意。