找到的排序的子序列中的置换 [英] Finding sorted sub-sequences in a permutation

问题描述

给定一个数组A持有的1,2，...，N置换。数组的子块 A [i..j] A 被称为如果所有的数字出现在一个有效的块 A [i..j] 是连续的数字（可能不妥当。

Given an array A which holds a permutation of 1,2,...,n. A sub-block A[i..j] of an array A is called a valid block if all the numbers appearing in A[i..j] are consecutive numbers (may not be in order.

由于数组 A = [7 3 4 1 2 6 5 8] 有效块 [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）的算法来计算有效的块数。

Give an O(n log n) algorithm to count the number of valid blocks.

推荐答案

下面是一个最坏情况下的为O（n log n）的分而治之算法。定的置换的一个非空的子列表，将其划分为左半，一个中间元件，和一个右半。递归地计算包含在左半块的数量和包含在右半块的数量。现在在O（n）的时间，计算块，其中包括中间的元件如下的数目

Here's a worst-case O(n log n) divide and conquer algorithm. Given a non-empty sublist of a permutation, divide it into a left half, a middle element, and a right half. Recursively compute the number of blocks contained in the left half and the number of blocks contained in the right half. Now in O(n) time, compute the number of blocks that include the middle element as follows.

观察到的两个有效块中的交集为空或者一个有效的块和整个置换是一个有效的块。总之，这些事实暗示的封的存在的：包含指定的（非相邻的）序列独特最小有效块。限定的向左扩展的是，中间元件的闭合和元件未在右半部。限定的右延伸的是，中间元件的闭合和元件未在左半。左扩展（分别是右扩展）是全序相对于所述子列表关系。它们可以通过简单的工作列表算法的手段来计算，以便在线性时间

Observe that the intersection of two valid blocks is either empty or a valid block and that the whole permutation is a valid block. Together, these facts imply the existence of closures: unique minimal valid blocks that contain a specified (non-contiguous) subsequence. Define a left extension to be a closure of the middle element and an element not in the right half. Define a right extension to be a closure of the middle element and an element not in the left half. The left extensions (respectively, the right extensions) are totally ordered with respect to the sublist relation. They can be computed in order in linear time by means of a simple work-list algorithm.

现在观察到的两个重叠有效阻止工会本身就是一种有效的块。予权利要求包含该中间元件每个有效块可以写成的由最左边的元件与由最右边的元件产生的右延伸产生的左延伸的联合。为了计算这种形式的联盟，遍历递增的顺序在左侧的扩展。保持指针的至少右延伸，其最右边的元件不留在左延伸的最右边的，并以至少其最左边的元件被留在左延伸的最左边的。因为单调性，这些指针只能移动到较大的扩展，所以总的工作是线性的。他们结合的上面和下面的资格伙伴当前左延伸。

Observe now that the union of two overlapping valid blocks is itself a valid block. I claim that every valid block containing the middle element can be written as the union of the left extension generated by the leftmost element with the right extension generated by the rightmost element. To count unions of this form, iterate through the left extensions in increasing order. Maintain pointers to the least right extension whose rightmost element is not left of the left extension's rightmost, and to the least whose leftmost element is left of the left extension's leftmost. Because of monotonicity, these pointers can only move to larger extensions, so the total work is linear. They bound above and below the eligible partners for the current left extension.

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()));
}

这篇关于找到的排序的子序列中的置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！