Нахождение отсортированных подпоследовательностей в перестановке

Я не думаю, что вам нужен алгоритм. Вот что вам нужно. Суммирование (от i = 0 до i = n-1) (n - i) * (i + 1)!

Это не совсем полное решение, но отправная точка для дальнейших размышлений.

Уловка, похоже, заключается в том, что набор всегда равен 1,2, ..., n, из чего ясно, что весь набор всегда является первым очевидно действительным блоком. Если вы начнете с этого полного набора и продвигаетесь вниз, его будет немного легче понять.

Набор с наиболее подходящими блоками: M = [1 2 3 4 5. . . n] , потому что каждое подмножество [i..j] гарантированно является допустимым блоком. M - хороший тестовый пример, потому что вы можете легко определить фактическое количество допустимых блоков: ((n - 1) / 2) * n .

Представьте, что у вас есть функция, которая, учитывая список из n целых чисел, может сказать вам, являются ли они допустимым блоком или нет.

Представьте, что вы изменили эту функцию так, что вместо этого она вернула количество сколько подблоков было действительным, поэтому, если [1 3 2 4] найдет [1 3 2 4], [1 3 2], [3 2 4], [3 2].

Чтобы внести это изменение, вы Я просто перебрал все возможные подблоки, передав их исходной функции, пока у вас не будет всего 2 чисел:

1,3,2,4 is valid
1,3,2 is valid
1,3 is NOT valid
3,2,4 is valid
3,2 is valid
There were 4 valid sub blocks

Первая функция, затем:

def isValid(li):
    return (max(li)-min(li) == len(li)-1) 

То есть, предполагая, что все значения разные, наибольшее значение минус наименьшее должна дать длину массива минус 1. Для [1 3 2 4] наибольшее = 4, наименьшее = 1, макс-мин = 3, длина-1 = 3, работа выполнена.

Основная функция проверки:

def countValidSubs(li):
    count = 0
    length = len(li)
    for start in range(0,length-2):
        for newlen in range(length-start,1,-1):
            newli = li[start:start+newlen]
            if isValid(newli):
                print(','.join(`i` for i in newli)+" is valid")
                count += 1
            else:
                print(','.join(`i` for i in newli)+" is NOT valid")
    return count

Тогда просто позвоните так:

countValidSubs([1, 3, 2, 4, 5, 7, 9, 8, 6])

(Ответьте там 14,кстати)

Единственная проблема с этим ответом в качестве домашнего задания состоит в том, что это O (n ² / 2)

Вот наихудший O(n log n) алгоритм "разделяй и властвуй". Получив непустой подсписок перестановки, разделите его на левую половину, средний элемент и правую половину. Рекурсивно вычислите количество блоков, содержащихся в левой половине, и количество блоков, содержащихся в правой половине. Теперь за время O(n) вычислите количество блоков, включающих средний элемент, следующим образом.

Обратите внимание, что пересечение двух допустимых блоков либо пусто, либо является допустимым блоком, и что вся перестановка является допустимым блоком. Вместе эти факты означают существование замыканий: уникальных минимальных допустимых блоков, которые содержат заданную (несмежную) подпоследовательность. Определим левое расширение как замыкание среднего элемента и элемента, не входящего в правую половину. Определите правое расширение как замыкание среднего элемента и элемента, не входящего в левую половину. Левые расширения (соответственно, правые расширения) полностью упорядочены по отношению к подсписку. Они могут быть вычислены по порядку за линейное время с помощью простого алгоритма рабочего списка.

Заметим теперь, что объединение двух пересекающихся валидных блоков само является валидным блоком. Я утверждаю, что каждый допустимый блок, содержащий средний элемент, может быть записан как объединение левого расширения, порожденного крайним левым элементом, с правым расширением, порожденным крайним правым элементом. Чтобы подсчитать объединения такой формы, пройдитесь по левым расширениям в порядке возрастания. Храните указатели на наименьшее правое расширение, крайний правый элемент которого не левее крайнего правого элемента левого расширения, и на наименьшее, крайний левый элемент которого левее крайнего левого расширения. В силу монотонности эти указатели могут переходить только к большим расширениям, поэтому общая работа линейна. Они связываются выше и ниже допустимых партнеров для текущего левого расширения.

C++ implementation:

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