寻找极端的优先功能/字母顺序 [英] Find the extreme for priority function / alphabet order

问题描述

我们有元素 A1，A2，... AN 从字母电子的数组。假设 | N | ＆GT;＆GT; | E |。

We have an array of elements a1,a2,...aN from an alphabet E. Assuming |N| >> |E|.

有关字母表中的每个符号，我们定义了一个唯一的整数优先级= V（符号）。让我们来定义 V {I}：= V（符号（AI））的简单

For each symbol of the alphabet we define an unique integer priority = V(sym). Let's define V{i} := V(symbol(ai)) for the simplicity.

如何才能找到的优先级功能，V代表其中：

How can I find the priority function V for which:

Count(i)->MAX | V{i} < V{i+1}

换句话说，我需要找到字母表中的优先级/置换为其位置数我，满足条件 V {我}＆LT; V {I + 1} ，是最大的。

In other words, I need to find the priorities / permutation of the alphabet for which the number of positions i, satisfying the condition V{i}<V{i+1}, is maximum.

修改-1：请仔细阅读。我给出一个数组 AI 和任务是生产函数 V 。它的不可以有关使用优先功能分类输入数组。

Edit-1: Please, read carefully. I'm given an array ai and the task is to produce a function V. It's not about sorting the input array with a priority function.

修改-2：实例

E = {A，B，C}; A ='abcab $'; （这里$ =人工终止符号，V {$} = +无穷大）

E = {a,b,c}; A = 'abcab$'; (here $ = artificial termination symbol, V{$}=+infinity)

其中一个最佳的优先级功能是： V {A} = 1，V {B} = 2，V {c}里= 3 ，这给了我们以下数组元素的迹象： A＆LT; B＆LT; C＆gt;在＆LT; B＆LT; $ ，造成4'＆LT;共有5个迹象。

One of the optimal priority functions is: V{a}=1,V{b}=2,V{c}=3, which gives us the following signs between array elements: a<b<c>a<b<$, resulting in 4 '<' signs of 5 total.

推荐答案

<打击>如果元素不可能并列的优先级，这将是微不足道的。只需按优先级排序。但是你可以有相同的优先级。

If elements could not have tied priorities, this would be trivial. Just sort by priority. But you can have equal priorities.

我会先进行排序的字母按优先级。然后我会提取最长的上升子序列。这就是你的答案的开始。提取剩下的最长上升子序列。追加，为你的答案。重复提取过程直到整个字母表已经提取

I would first sort the alphabet by priority. Then I'd extract the longest rising subsequence. That is the start of your answer. Extract the longest rising subsequence from what remains. Append that to your answer. Repeat the extraction process until the entire alphabet has been extracted.

我认为，这给出了一个最佳的结果，但我还没有尝试证明这一点。如果不是完美最佳的，但它仍然会pretty的良好

I believe that this gives an optimal result, but I haven't tried to prove it. If it is not perfectly optimal, it still will be pretty good.

现在，我想我明白这个问题，我可以告诉你，有没有好的算法来解决这个问题。

Now that I think I understand the problem, I can tell you that there is no good algorithm to solve it.

要看到这让我们首先构造一个有向图的顶点是你的元素，且其边表示多少次一个元素立刻preceeded另一回事。您可以创建通过删除足够多的边沿获得一个向无环图优先功能，使用边缘以创建一个偏序集，然后直到你有一个完整的线性顺序，从中你可以平凡得到优先功能添加顺序关系。所有这一切很简单，一旦你已经想通了其边缘下降。相反因为向图和最终优先功能，很容易找出哪些边集，你不得不决定放弃。

To see this let us first construct a directed graph whose vertices are your elements, and whose edges indicate how many times one element immediately preceeded another. You can create a priority function by dropping enough edges to get a directed acyclic graph, use the edges to create a partially ordered set, and then add order relations until you have a full linear order, from which you can trivially get a priority function. All of this is straightforward once you have figured out which edges to drop. Conversely given that directed graph and your final priority function, it is easy to figure out which set of edges you had to decide to drop.

所以你的问题是完全等同于计算出一组边的最小你需要从<打击>砸的有向图让<打击> A 的向无环图。然而，随着 http://en.wikipedia.org/wiki/Feedback_arc_set 说，这是一个已知NP难问题称为最小反馈弧集。 开始更新因此，它是不太可能有一个很好的算法，就可以拿出图表。 末更新

Therefore your problem is entirely equivalent to figuring out a minimal set of edges you need to drop from athat directed graph to get athat directed acyclic graph. However as http://en.wikipedia.org/wiki/Feedback_arc_set says, this is a known NP hard problem called the minimum feedback arc set. begin update It is therefore very unlikely that there is a good algorithm for the graphs you can come up with. end update

如果您需要解决它在实践中，我建议去为某种贪心算法。它不会永远是正确的，但它通常会给有些合理的结果在合理的时间。

If you need to solve it in practice, I'd suggest going for some sort of greedy algorithm. It won't always be right, but it will generally give somewhat reasonable results in reasonable time.

更新：的白痴是正确的，我没有证明NP难。不过也有很好的启发有理由相信，问题是，实际上，NP难。查看评论更多。

Update: Moron is correct, I did not prove NP-hard. However there are good heuristic reasons to believe that the problem is, in fact, NP-hard. See the comments for more.

这篇关于寻找极端的优先功能/字母顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！