题

我需要一个算法，可图的运行在一个置换到一个单一的数量，也降低后的数字。

因此，一个运行顺序的集的数排列，排和顺序。在该列表中, 1;2;3;5;6;4 有两个运行中，1；2个；3和5;6.我想代替这些与一个单一的数量、最低限度，所以，如果之后，除去运行，我们有一个排列的4个要素，置换使用数字1...4.在上述情况，我们必须减少这两个运行。第一次运行将1,4转换到2，[5条；第6]转至3日举行的第二次标准。如果我种的减排列然后展开的元素内从映射，并且排序的原置换我会得到相同的结果。所得到的排列不应该有任何运行。

例如(我已经强调了运行):

(1;2;3;4;5;6) => 1 //Mappings: 1->1;2;3;4;5;6
(2;3;4);1;(5;6) => 2 1 3 // Mappings: 2->2;3;4, and 3->5;6
(3;4);(1;2);(5;6) => 2 1 3 // Mappings: 2->3;4, and 1->1;2 and 3->5;6

现在，我通过在名单和制作的列表，列表、分组的运行。真的第二部分是对困难的部分做一个干净的解决方案。我已经想到了天真的做法，很好奇如果任何人有一些聪明的技巧，可以做的更好然后我的，我在等O(2n+n记录n)，

  • 更换的运行带头元的运行，并插入数据到一个hashtable(可恢复性)
  • 排序，以创建一个地图以丢失的数字与它的排索引。[1;6;5;4]将输出[(1,1);(4,2);(5,3);(6,4)]
  • 替换清单在第1步与创建的地图中的步骤2和更新hashtable进行翻译。

通过运行实例，再次：

step 1: replace runs with the head element of the run and inserting data into a hash table  
    [1;3;4;2;5;6;] -> [1;3;2;5]  
step 2: sort array to create map  
    [1235], so we know that, in the previous array, 1 maps to 1, 2 to 2, 3 to 3, 4 to 5.  
step 3: do above translation on array from step one. 
    [1;3;2;4]

如果我对此排列和重建:[1;2;3;4], 3->3;4 4>5条；第6我, 1;2;3;4;5;6.还排序。

我使用的是名单，这样一种功能性做法将是首选。没有代码必要的。所有的想法，当然值得欢迎的。

编辑：

mweerden:

这我不清楚什么样的确切条件上映射。为什么究竟是不是允许的，只要产生排列[1,2,...,N]对一的置换N运行?你似乎更愿意图的一个运行的数字运行，但(为这并不总是可能的)你似乎允许某些自由。–

我不喜欢地图运行一些内运行(看上面!), 但我需要保留一个 订购.置换[1；2个；3个...N] 是 一个运行，并因此可进一步下降。这就是为什么它是无效的。所以问题将在进一步行动的另一个算法，但是个别要素可能扩大在最后的救援的原始排列。

有帮助吗？

解决方案

符号：

  • 开始计数在1
  • l.i 是的元素 i 列表 l
  • l+m 是串联的名单 l 和 m
  • 一个运行是一个最大的子列表，一个列表 [n,n+1,n+2,...,m] 对于一些 n 和 m 与 n <= m

所以我们都给予了排列 p 列表 [1,2,...,N].我们把 p 进入运行 r_1,r_2,...,r_M 这样， p = r_1+r_2+...+r_M.我们再找一个置换 q 的 [1,2,...,M] 这样， r_(q.1)+r_(q.2)+...+r_(q.M) = [1,2,...,N].

例如，如果 p = [1,3,4,2,5,6], 我们有 N=6, M=4, r_1 = [1], r_2 = [3,4], r_3 = [2] 和 r_4 = [5,6].在这种情况下，我们需要 q 要 [1,3,2,4] 作为 r_1+r_3+r_2+r_4 = [1]+[2]+[3,4]+[5,6] = [1,2,3,4,5,6].

注意， q 不能包含的长度大于每一个定义；如果会，那么有一个 i < M 与 q.i + 1 = q.(i+1) 和这样一个子列表 r_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1) 的 [1,2,...,N], 但 r_(q.i)+r_(q.i + 1) 也是一个子列表中的 p 这违背了， r_(q.i) 和 r_(q.i + 1) 是运行。

现在，找到一个 q 给一个 p, 我们假设性的映射数据结构 O(1) 插入和查询的数字和列表 O(1) 追加的和向前穿越。然后我们做到以下几点。

  • 首先，我们建造的名单 runheads = [r_1.1,r_2.1,...,r_M.1].这可以通过平凡的历 p 虽然维持目前的运行。在这一步中，我们还记得的最大数目中遇到的获取 N 在结束建造一映射 heads 与的元素 runheads 作为键。这一步骤是清楚的 O(n).注意，它不是有关什么的价值 heads 是的，所以我们只能使用运行 r_i 作价值的关键 r_i.1.

  • 接下来，我们从迭代 1 至(包括) N 维持一个值 k 与初始价值 1.每个的价值 i 我们检查看看 i 在 heads.如果是这种情况下，我们加入 i -> k 为映射 f 和增加 k.这一步骤也是清楚的 O(n).能够回来 q 要 p 我们还可以存储额外的映射 rev 与 k -> i 甚至 k -> runheads(i) 在没有额外的大O成本。

  • 最后，我们适用的映射 f 元素 runheads 得到 q.再一次 O(n).

为了说明一个例子我们来看看情况， p = [1,3,4,2,5,6].

  • 在第一个步骤，我们得到 runheads = [1,3,2,5], N=6 和 heads = { 1 -> [1], 3 -> [3,4], 2 -> [2], 5 -> [5,6] }.

  • 第二个步骤，我们四个情况下，我们必须做一些事情： 1, 2, 3 和 5.对于这些情况下，我们有值 k 那是 1, 2, 3 和 4, 分别。这意味着 f 将 { 1 -> 1, 2 -> 2, 3 -> 3, 5 -> 4 }.(及 rev 将会是 { 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 5 } 或 { 1 -> [1], 2 -> [2], 3 -> [3,4], 4 -> [5,6] }, 根据什么你选择了商店。)

  • 得到 q 我们计算出 map(f,runheads) 这是 [f(1),f(3),f(2),f(5)] 或者等价的， [1,3,2,4].

所以，如果我没犯了一个错误，如果数据结构满足上述要求，这种解决方案应该是 O(n).注意，在实践中，这实际上可能更有用的使用自己的(O(n*log(n)))的解决方案。如果你有一个很大的 p 但只有一对夫妇的运行，分类 runheads 和使用，以建立的映射可能会更有效率。我不认为 p 会有相当大，这是这种情况。

其他提示

编辑clarificaton

步骤1：运算法而产生只有一个哈希表产生了希表(D1)编制索引的设置就是映射(例如，对于[3,4]，这将是3)和一览表(1)与设定本身

[3;4;6;8;1;2]:

   D1              L1

3 -> [3,4]     1 -> [3,4]

6 -> [6]       2 -> [6]

8 -> [8]       3 -> [8]

1 -> [1,2]     4 -> [1,2]

步骤2：我你看集我们现在有你会看到，对于给定我们的指数中，我们发现它(在L1)以及头部的价值。正确的地图的价值将最低整数之间他们不是已经采取。例如，对于在[第3、4]我们的价值必须1和3之间，而且，由于1已经采取相应的价值为2。考虑到，D1索引的头值，低值将被直在采取，如果相应的设定存在。在该实例中，[1,2]映射1，以使这一关键的是已经"采取"。因此，在伪:

for (int Current = 1; Current  < L1.Length; Current++)
{
  GetHead(L1[Current]);
  Index = Current;
  While Head > Index
  {
    if D1.Empty(Index)
    {
      D1.Add(Index,D2[Current])
      D1.DeleteIfNotEmpty(Head);
    }
    else
      Index++;
  }
}

例如

  • 我们采取的第一个价值在L1->[3,4]...
  • 获得头=3
  • 开始月1.我们查找D1[1]而已经采取的，所以我们增加到2。
  • 我们寻找D1[2]其是空的，所以我们分配D1[2]=[3,4]和删除D[3]

不提供O(n)但是喜欢的东西O(n+日志(n))(n为第一步，日志(n)的第二个)

为上面的例子，让你：

1 -> [1,2]
2 -> [3,4]
3 -> [6]
4 -> [8]

现在，如果你有[3;4;8;6;1;2], 这将导致在

1 -> [1,2]
2 -> [3,4]
3 -> [8]
4 -> [6]

因为它是使用绝对排序在原来的阵，我不知道如果这是所有权或者你只想要6至可以在指标3和8的是在指数4，在这种情况下，你可能不得不预L1基于头，这将增加你的复杂性日志(n)

如果你有预约只有0(n+日志^2(n))它不是那么坏(不假定一个快速排序已O(日志n)订购L1将O(日志(日志n))

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top