我们有a1,a2,...aN一个字母表中的元素数组E.假设|N| >> |E|.
对于字母表的每个符号,我们定义一个唯一的整数优先级= V(sym).让我们来定义V{i} := V(symbol(ai))简单性.
如何找到优先级函数V:
Count(i)->MAX | V{i} < V{i+1}
换句话说,我需要找到i满足条件的位置数量V{i}<V{i+1}最大的字母表的优先级/排列.
编辑-1:请仔细阅读.我给了一个数组ai,任务是生成一个函数V.它不是用优先级函数对输入数组进行排序.
编辑-2:示例
E = {a,b,c}; A = 'abcab$'; (此处$ =人工终止符号,V {$} = +无穷大)
最佳优先级函数之一是:V{a}=1,V{b}=2,V{c}=3,它给出了数组元素之间的以下符号:,总共得出a<b<c>a<b<$5'符号.
如果元素不能绑定优先级，那么这将是微不足道的。只需按优先级排序即可。但你们可以拥有同等的优先权。
我首先会按优先级对字母表进行排序。然后我会提取最长的上升子序列。这就是你的答案的开始。从剩下的部分中提取最长的上升子序列。将其附加到您的答案中。重复提取过程，直到提取出整个字母表。
我相信这会给出最佳结果，但我还没有尝试证明这一点。即使它不是完美的最优，它仍然会相当不错。
现在我想我明白了这个问题，我可以告诉你，没有好的算法可以解决它。
为了了解这一点，让我们首先构造一个有向图，其顶点是您的元素，其边指示一个元素紧接在另一个元素之前的次数。您可以通过删除足够的边来创建优先级函数，以获得有向无环图，使用边创建部分有序集，然后添加顺序关系，直到获得完整的线性顺序，从中您可以轻松获得优先级函数。一旦你弄清楚要放弃哪些边缘，所有这一切都变得很简单。相反，鉴于有向图和最终的优先级函数，很容易找出您必须决定放弃哪一组边。
因此，您的问题完全等同于找出需要从该有向图中删除以获得该有向无环图所需的最小边集。然而，正如http://en.wikipedia.org/wiki/Feedback_arc_set所说，这是一个已知的 NP 难题，称为最小反馈弧集。 开始更新因此，您不太可能为图表找到一个好的算法。结束更新
如果您需要在实践中解决它，我建议采用某种贪婪算法。它并不总是正确的，但通常会在合理的时间内给出合理的结果。
更新：白痴是正确的，我没有证明 NP 困难。然而，有充分的启发性理由相信这个问题实际上是 NP 困难的。更多内容请参阅评论。