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

Question

Учитывая массив A, который содержит перестановку 1,2, ..., n. Сборочный блок A[i..j] массива A называется правильный блок, если все числа, входящие в A[i..j] являются последовательными числами (не может быть в порядке.

Дан массив 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), чтобы подсчитать количество допустимых блоков.

Answer 1

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

Answer 2

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

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

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

Answer 3

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

Представьте, что вы изменили эту функцию, вместо этого вернули подсчет количества подблоков, поэтому [1 3 2 4] найдет [1 3 2 4], [1 3 2], [3 2 4 ], [3 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, max-min = 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)

Answer 4

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

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

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

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