algorithm - 减少排列

Question

我需要一种算法，可以将排列中的游程映射到单个数字，同时减少后续数字。

因此，运行是按排列顺序排列的一组连续数字。在列表 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 中创建的 map 并更新哈希表以进行翻译。

再次运行示例:

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:

It's not clear to me what the precise conditions on the mapping are. Why exactly isn't it allowed to just produce the permutation [1,2,...,N] for a permutation with N runs? You seem to prefer to map a run to a number from that run, but (as this isn't always possible) you seem to allow some freedom. –

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

Answer 1

符号:

• 从 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每个定义不能包含长度大于 1 的游程；如果可以，那么就有一个 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 的元素作为 key 。这一步很明显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情况必须非常大。