减少排列

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日志n），

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

通过一个例子，再次：

 
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：

目前尚不清楚对我有什么对测绘精确的条件。为什么不允许为N次运行的置换生成置换[1,2，...，N]？你似乎更喜欢将跑步映射到跑步中的一个数字，但是（因为这并非总是可行），你似乎允许一些自由。 -

我不喜欢跑步映射到运行中的一些（看上面！），但我需要保持一个订购。置换[1; 2; 3 ... N] 为一次运行，因此可以进一步降低。这就是为什么它是无效的。这个顺序在另一个算法的进一步操作中很重要，但是单个元素可以在最后扩展以挽救原始排列。

Answer 1

记号：

• 计数从1开始
• l.i是列表l
• l+m的元素i被列出l的级联和m
• 运行是一个最大的子列表是对一些n和m的列表[n,n+1,n+2,...,m]与n <= m

所以我们给出列表[1,2,...,N]的排列p。我们将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)因而[1,2,...,N]子列表r_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1)，但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必须是相当大的，因为这是事实。

Answer 2

被修改为clarificaton

步骤1：运行算法但不是只产生一个哈希表产生由该组的头索引的哈希表（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由头部索引值，如果相应的设置存在，则总是会采用较低的值。在这个例子中，[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），但像Ø第（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，在这种情况下，您可能会有（n）

如果你必须预先订购，你将有0（n + log^2（n）），这不是很糟糕（也许更少假设快速排序为O（log n）的订货L1将O（日志（log n）的）