1

我需要一种算法，可以将排列中的运行映射到单个数字，但也可以减少后续数字。

因此，运行是排列中有序且有序的一组连续数字。在列表中，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 log n)，

  • 用运行的头元素替换运行并将该数据插入哈希表（用于可恢复性）
  • 排序以使用其排序索引创建缺失数字的映射。[1;6;5;4] 将输出 [(1,1);(4,2);(5,3);(6,4)]
  • 将步骤 1 中的列表替换为步骤 2 中创建的地图并更新哈希表以进行翻译。

再次运行一个例子：

步骤 1：用运行的头元素替换运行并将数据插入哈希表  
    [1;3;4;2;5;6;] -> [1;3;2;5]  
第 2 步：排序数组以创建地图  
    [1235]，所以我们知道，在前面的数组中，1 映射到 1、2 到 2、3 到 3、4 到 5。  
第 3 步：从第 1 步开始对数组进行上述翻译。
    [1;3;2;4]

如果我对这个排列进行排序并重构：[1;2;3;4], 3->3;4 和 4->5;6 我得到 1;2;3;4;5;6。也排序了。

我正在使用列表，因此首选功能方法。无需代码。当然，欢迎所有想法。

编辑：

默维尔登：

我不清楚映射的精确条件是什么。为什么不允许只为具有 N 次运行的排列生成排列 [1,2,...,N]？您似乎更喜欢将运行映射到该运行的数字，但是（因为这并不总是可能的）您似乎允许一些自由。–

我不喜欢将一个运行映射到该运行中的一个数字（见上图！），但我需要保留一个ordering。排列 [1;2;3...N]是一次运行，因此可以进一步减少。这就是它无效的原因。该顺序将在另一个算法的进一步操作中很重要，但可以在最后扩展各个元素以挽救原始排列。

4

2 回答 2

2

符号：

  • 从 1 开始计数
  • l.ii是列表的元素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_Mp = r_1+r_2+...+r_Mq[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]和。在这种情况下，我们需要as 。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每个定义不能包含长度大于 1 的游程；如果是这样，那么有一个i < Mwithq.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与 that 相矛盾的子列表，r_(q.i)并且r_(q.i + 1)是运行。

现在，为了找到q给定的 a ，我们假设具有插入和查找数字p的映射数据结构以及带有追加和前向遍历的列表的可用性。然后我们执行以下操作。O(1)O(1)

  • 首先我们构造列表runheads = [r_1.1,r_2.1,...,r_M.1]。p这可以通过在保持当前运行的同时进行遍历来轻松完成。在这一步中，我们还记得最后遇到的最大数，并以 的元素作为键N构建映射。这一步很清楚。请注意，它的值是什么无关紧要，因此我们可以将 run用作 key 的值。headsrunheadsO(n)headsr_ir_i.1

  • 接下来我们迭代从1到（包括）N维护一个k具有初始值的值1。对于每个值i，我们检查是否i在heads. 如果是这种情况，我们添加i -> k到映射f并增加k。这一步也很清楚O(n)。为了能够从qto返回，p我们还可以存储一个额外的映射rev，k -> i甚至k -> runheads(i)不需要额外的 big-O 成本。

  • 最后，我们将映射应用于to getf的元素。再次。runheadsqO(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和。对于这些情况，我们的值分别是、和。这意味着将是。（并且会是or ，具体取决于您选择存储的内容。）35k1234f{ 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必须是相当大的。

于 2009-01-26T23:17:45.383 回答
0

为澄清而编辑

第 1 步：运行算法，但不是只生成一个哈希表，而是生成一个哈希表 (D1)，该哈希表 (D1) 由它映射到的集合的头部索引（例如，对于 [3,4]，它将是 3）和一个列表(L1) 与集合本身

[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 中）和 Head 值。正确的地图值将是它们之间尚未采用的最小整数。例如，对于 [3,4]，我们将拥有该值必须介于 1 和 3 之间，并且由于已经采用 1，因此相应的值为 2。考虑到，由于 D1 由 Head 索引值，如果存在相应的集合，则始终采用较低的值。在这个例子中，[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+log(n)) （第一步为 n，第二步为 log(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基于头部，这将使您的复杂性增加 Log(n)

如果您必须预订，您将拥有 0(n+log^2(n)) ，这还不错（假设 QuickSort 有 O(Log n) 排序 L1 将是 O(log(log n))

于 2009-01-26T18:45:07.993 回答