algorithm - 在排列中查找已排序的子序列

Question

给定一个数组 A，其中包含 1,2,...,n 的排列。数组 A 的子 block A[i..j]如果 A[i..j] 中出现的所有数字都是连续的数字(可能不按顺序)，则称为有效 block 。

给定一个数组 A= [ 7 3 4 1 2 6 5 8]有效 block 是 [3 4]、[1,2]、[6,5]、[3 4 1 2]、[3 4 1 2 6 5]、[7 3 4 1 2 6 5]、 [7 3 4 1 2 6 5 8]

给出一个 O(n log n) 的算法来计算有效 block 的数量。

Answer 1

这是最坏情况下的 O(n log n) 分而治之算法。给定一个排列的非空子列表，将其分为左半部分、中间元素和右半部分。递归计算左半部分包含的 block 数和右半部分包含的 block 数。现在在 O(n) 时间内，计算包含中间元素的 block 数如下。

观察两个有效 block 的交集要么是空 block 要么是有效 block ，并且整个排列都是有效 block 。总之，这些事实意味着存在闭包:包含指定(非连续)子序列的唯一最小有效 block 。定义一个 left extension 是中间元素和不在右半部分的元素的闭包。定义一个右扩展作为中间元素和不在左半部分的元素的闭包。左扩展(相应地，右扩展)相对于子列表关系是完全有序的。它们可以通过简单的工作列表算法在线性时间内按顺序计算。

现在观察两个重叠的有效 block 的并集本身就是一个有效 block 。我声称每个包含中间元素的有效 block 都可以写成最左边元素生成的左扩展与最右边元素生成的右扩展的并集。要计算这种形式的并集，请按递增顺序遍历左侧扩展。维护指向最右元素不在左扩展最右元素左侧的最右扩展的指针，以及指向最左元素不在左扩展最左元素左侧的指针。由于单调性，这些指针只能移动到更大的扩展，所以总的工作是线性的。它们在当前左侧扩展的合格合作伙伴上方和下方绑定(bind)。

C++ 实现:

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stdexcept>
#include <vector>

namespace {
typedef std::vector<int> IntVector;

struct Interval {
  int left;
  int right;
};

Interval MakeInterval(int left, int right) {
  Interval i = {left, right};
  return i;
}

typedef std::vector<Interval> IntervalVector;

enum Direction {
  kLeft,
  kRight,
};

// Finds the valid intervals obtained by starting with [pi[mid],
// pi[mid]] and repeatedly extending in direction dir
//
// O(right_boundary - left_boundary)
void FindExtensions(const IntVector& pi, const IntVector& pi_inv,
                    int left_boundary, int right_boundary,
                    Direction dir, IntervalVector* extensions) {
  int mid = left_boundary + (right_boundary - left_boundary) / 2;
  int left = mid;
  int right = mid;
  int lower = pi[mid];
  int upper = pi[mid];
  std::queue<int> worklist;
  while (true) {
    if (worklist.empty()) {
      extensions->push_back(MakeInterval(left, right));
      if (dir == kLeft) {
        if (left == left_boundary) break;
        --left;
        worklist.push(left);
      } else {
        if (right == right_boundary) break;
        ++right;
        worklist.push(right);
      }
    } else {
      int i = worklist.front();
      worklist.pop();
      if (i < left) {
        if (i < left_boundary) break;
        for (int j = left - 1; j >= i; --j) worklist.push(j);
        left = i;
      } else if (right < i) {
        if (right_boundary < i) break;
        for (int j = right + 1; j <= i; ++j) worklist.push(j);
        right = i;
      }
      int x = pi[i];
      if (x < lower) {
        for (int y = lower - 1; y > x; --y) worklist.push(pi_inv[y]);
        lower = x;
      } else if (upper < x) {
        for (int y = upper + 1; y < x; ++y) worklist.push(pi_inv[y]);
        upper = x;
      }
    }
  }
}

int CountValidRecursive(const IntVector& pi, const IntVector& pi_inv,
                        int left, int right) {
  if (right < left) return 0;
  int mid = left + (right - left) / 2;
  int count = CountValidRecursive(pi, pi_inv, left, mid - 1) +
      CountValidRecursive(pi, pi_inv, mid + 1, right);
  IntervalVector left_exts;
  FindExtensions(pi, pi_inv, left, right, kLeft, &left_exts);
  IntervalVector right_exts;
  FindExtensions(pi, pi_inv, left, right, kRight, &right_exts);
  typedef IntervalVector::const_iterator IVci;
  IVci first_good = right_exts.begin();
  IVci first_bad = right_exts.begin();
  for (IVci ext = left_exts.begin(); ext != left_exts.end(); ++ext) {
    while (first_good != right_exts.end() && first_good->right < ext->right) {
      ++first_good;
    }
    if (first_good == right_exts.end()) break;
    while (first_bad != right_exts.end() && ext->left <= first_bad->left) {
      ++first_bad;
    }
    count += std::distance(first_good, first_bad);
  }
  return count;
}

// Counts the number of intervals in pi that consist of consecutive
// integers
//
// O(n log n)
int CountValid(const IntVector& pi) {
  int n = pi.size();
  IntVector pi_inv(n, -1);
  // Validate and invert pi
  for (int i = 0; i < n; ++i) {
    if (pi[i] < 0 || pi[i] >= n || pi_inv[pi[i]] != -1) {
      throw std::runtime_error("Invalid permutation of {0, ..., n - 1}");
    }
    pi_inv[pi[i]] = i;
  }
  return CountValidRecursive(pi, pi_inv, 0, n - 1);
}

// For testing purposes
int SlowCountValid(const IntVector& pi) {
  int count = 0;
  int n = pi.size();
  for (int left = 0; left < n; ++left) {
    for (int right = left; right < n; ++right) {
      int lower = pi[left];
      int upper = pi[left];
      for (int i = left + 1; i <= right; ++i) {
        if (pi[i] < lower) {
          lower = pi[i];
        } else if (pi[i] > upper) {
          upper = pi[i];
        }
      }
      if (upper - lower == right - left) ++count;
    }
  }
  return count;
}
}  // namespace

int main() {
  int n = 10;
  IntVector pi(n);
  for (int i = 0; i < n; ++i) pi[i] = i;
  do {
    if (SlowCountValid(pi) != CountValid(pi)) {
      fprintf(stderr, "Bad permutation:");
      for (IntVector::const_iterator x = pi.begin(); x != pi.end(); ++x) {
        fprintf(stderr, " %d", *x);
      }
      fputc('\n', stderr);
    }
  } while (std::next_permutation(pi.begin(), pi.end()));
}