问计算排列中有效块数量的算法

EN

好了，我只剩下1个代表了，因为我在一个相关的问题上放了200个赏金：Finding sorted sub-sequences in a permutation，所以我暂时不能发表评论。

我有一个想法: 1)定位所有的置换群。它们是：(78)，(34)，(12)，(65)。与群论不同，它们的顺序和位置以及它们是否相邻是重要的。因此，组(78)可以被表示为结构(7, 8, false)，而(34)将被表示为(3,4,true)。我正在使用Python的元组表示法，但实际上对组使用整个类可能更好。在这里，true或false表示连续或非连续。如果为(max(gp1) == min(gp2) + 1 or max(gp2) == min(gp1) + 1) and contigous(gp1) and contiguos(gp2)，则两个组是“相邻的”。这并不是union(gp1, gp2)连续的唯一条件，因为(14)和(23)很好地结合到了(14)中。对于algo课堂作业来说，这是一个很好的问题，但对于面试来说，这是一个很糟糕的问题。我怀疑这是家庭作业。

这个问题确实涉及到一些“数学技巧”，但一旦你得到了它，它就相当简单了。然而，我的解决方案的其余部分将不符合O(n log n)标准。

数学部分

对于任意两个连续的数字，它们的和是2k+1，其中k是最小的元素。对于三个数字是3k+3，对于四个数字是4k+6，对于N这样的数字是Nk + sum(1,N-1)。因此，您需要两个可以同时完成的步骤：

sub-arrays.

• Determine

1. 创建所有元素的和，子数组的最小元素。

对动态编程部分进行

使用前一行的条目的结果构建两个表，以构建每一连续行的条目。不幸的是，我完全错了，因为这仍然需要n^2个子数组检查。啊！

我的建议

STEP =2 //检查数量

B 0,0,0,0,0,0,0,0

B 1,1,0,0,0,0,0,0

有效(A，B) -如果无效，则移动一个

B 0,1,1,0,0,0,0,0

有效(A，B) -如果有效，则移动一步

B 0，0，0，1，0，0，0

有效(A，B)

B 0，0，0，0，1，1，0

步骤=3

B 1,1,1,0,0,0,0,0不好

B 0,1,1,1,0,0,0,0 ok

B 0，0，0，1，1，1，0不好

步骤=4

B 1,1,1,1,0,0,0,0不好

B 0,1,1,1,1,0,0,0 ok

.

CON <- 0
STEP <- 2
i <- 0
j <- 0
WHILE(STEP <= LEN(A)) DO
 j <- STEP
 WHILE(STEP <= LEN(A) - j) DO
  IF(VALID(A,i,j)) DO
   CON <- CON + 1
   i <- j + 1
   j <- j + STEP
  ELSE
   i <- i + 1
   j <- j + 1
  END
 END
 STEP <- STEP + 1
END

有效方法检查所有元素是否连续

从未测试过，但可能是正常的