Tìm các chuỗi con được sắp xếp theo hoán vị

Question

Cho một mảng A có hoán vị là 1,2, ..., n. Một tiểu khối A[i..j] của một mảng A được gọi là một khối hợp lệ nếu tất cả những con số xuất hiện trong A[i..j] là những con số liên tiếp (có thể không theo thứ tự.

Với một mảng A= [ 7 3 4 1 2 6 5 8] các khối hợp lệ là [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]

Cung cấp cho một thuật toán O (n log n) để đếm số lượng các khối hợp lệ

Answer 1

Tôi không nghĩ rằng bạn cần một thuật toán.Đây là những gì bạn cần Tổng kết (i = 0 to i = n-1) (n - i) * (i + 1)!

Answer 2

Đây không phải là một giải pháp hoàn toàn đầy đủ, nhưng là một điểm khởi đầu cho nhiều suy nghĩ hơn.

Bí quyết dường như nằm trong thực tế là tập hợp luôn là 1,2, ..., n từ đó rõ ràng là toàn bộ tập hợp luôn là khối đầu tiên rõ ràng hợp lệ. Nếu bạn bắt đầu từ đó tập hợp đầy đủ và làm việc theo cách của bạn xuống, nó có vẻ là một chút dễ dàng hơn để nắm bắt.

Tập hợp có các khối hợp lệ nhất là M = [1 2 3 4 5 . . . n] vì mỗi tập hợp con [i..j] được đảm bảo là một khối hợp lệ. M là một trường hợp thử nghiệm tốt vì bạn có thể dễ dàng xác định số lượng các khối hợp lệ thực tế: ((n - 1)/2) * n.

Answer 3

Hãy tưởng tượng bạn có một hàm, với danh sách n số nguyên có thể cho bạn biết liệu chúng có phải là một khối hợp lệ hay không.

Hãy tưởng tượng bạn đã sửa đổi chức năng này để thay vào đó đếm số lượng khối phụ hợp lệ, vì vậy [1 3 2 4] sẽ tìm [1 3 2 4], [1 3 2], [3 2 4 ], [3 2].

Để thực hiện thay đổi đó, bạn sẽ chỉ lặp qua tất cả các khối tiểu có thể, chuyển chúng tới các chức năng ban đầu cho đến khi bạn vừa 2 con số:

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 

Chức năng đầu tiên sau đó:

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

Tức là tất cả các giá trị khác nhau, giá trị lớn nhất trừ đi giá trị nhỏ nhất sẽ cho độ dài của mảng trừ đi 1. Đối với [1 3 2 4], lớn nhất = 4, nhỏ nhất = 1, max-min = 3, length-1 = 3, hoàn thành công việc.

Chức năng kiểm tra chính:

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 

Sau đó, chỉ cần gọi như:

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

(trả lời có 14, bằng cách này)

Vấn đề duy nhất với điều này như một bài tập về nhà câu trả lời là nó là O (n /2)

Answer 4

Đây là trường hợp xấu nhất O (n log n) giải thuật phân chia và chinh phục. Đưa ra một danh sách con không trống của một hoán vị, chia nó thành nửa trái, phần tử ở giữa và nửa bên phải. Đệ quy tính toán số lượng khối chứa trong nửa bên trái và số lượng khối chứa trong nửa bên phải. Bây giờ trong thời gian O (n), tính toán số khối bao gồm phần tử ở giữa như sau.

Quan sát rằng giao điểm của hai khối hợp lệ là ô trống hoặc khối hợp lệ và toàn bộ hoán vị là một khối hợp lệ. Cùng với nhau, những sự kiện này ngụ ý sự tồn tại của đóng cửa: các khối hợp lệ tối thiểu duy nhất chứa một chuỗi được chỉ định (không tiếp giáp). Xác định phần mở rộng bên trái là phần đóng của phần tử ở giữa và phần tử không nằm trong nửa bên phải. Xác định tiện ích mở rộng phải là để đóng thành phần giữa và phần tử không nằm trong nửa bên trái. Các phần mở rộng bên trái (tương ứng, các phần mở rộng phù hợp) được đặt hàng hoàn toàn đối với mối quan hệ danh sách con. Chúng có thể được tính theo thứ tự thời gian tuyến tính bằng một thuật toán danh sách công việc đơn giản.

Quan sát bây giờ rằng sự kết hợp của hai khối hợp lệ trùng lặp chính nó là một khối hợp lệ. Tôi cho rằng mỗi khối hợp lệ chứa phần tử ở giữa có thể được viết dưới dạng liên kết của phần mở rộng bên trái được tạo bởi phần tử ngoài cùng bên trái với phần mở rộng phù hợp được tạo bởi phần tử ngoài cùng bên phải. Để đếm các công đoàn của biểu mẫu này, hãy lặp qua các phần mở rộng bên trái theo thứ tự tăng dần. Duy trì các con trỏ đến phần mở rộng nhỏ nhất bên phải có phần tử ngoài cùng bên phải không nằm bên phải của phần ngoài cùng bên phải của phần mở rộng bên trái và phần tử con ngoài cùng bên trái của phần mở rộng bên trái là phần ngoài cùng bên trái. Do tính đơn điệu, các con trỏ này chỉ có thể di chuyển đến các phần mở rộng lớn hơn, do đó tổng số công việc là tuyến tính. Họ ràng buộc ở trên và bên dưới các đối tác đủ điều kiện cho tiện ích mở rộng bên trái hiện tại.

C++ thực hiện:

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