Chuỗi xa, chuyển vị chỉ

Question

thể trùng lặp:
Counting the swaps required to convert one permutation into another

Tôi đang tìm một thuật toán mà sẽ đếm một số loại khoảng cách chuỗi nơi duy nhất được phép hoạt động là vận dụng hai liền kề nhân vật. Ví dụ:
string1: "mother"
string2: "moterh"
khoảng cách: 2 (hoán đổi đầu tiên "h" với "e" và nhận "motehr" và sau đó "h" với "r" dẫn đến "moterh ")
Tôi biết rằng khoảng cách Damerau – Levenshtein khá giống với vấn đề đó, tuy nhiên nó đòi hỏi nhiều bộ nhớ (tôi muốn nó hoạt động khá nhanh trên các từ lên tới 1 000 000 ký tự). Tôi đã viết điều này:

int amo = 0; 

for (int i = 0; i < n; i++) 
{ 
    if (fromString[i] == toString[i]) 
     continue; 
    char toWhat = toString[i]; 
    int where = -1; 
    for (int j = i; j < n; j++) 
    { 
     if (fromString[j] == toWhat) 
     { 
      where = j; 
      break; 
     } 
    } 
    while (where != i) 
    { 
     char temp = fromString[where]; 
     fromString[where] = fromString[where - 1]; 
     fromString[where - 1] = temp; 
     where--; 
     amo++; 
    } 
} 
cout << amo << endl;` 

Chuỗi được biểu diễn bằng char [n] trong đó n là chiều dài của chúng. Tôi khá chắc chắn có một cách để làm điều đó nhanh hơn và tôi sẽ rất biết ơn nếu ai đó sẽ cho tôi biết làm thế nào để làm điều đó hoặc viết một số mã nguồn (tốt nhất sẽ là Java/Python/C++ nhưng bất cứ điều gì là tuyệt vời).

P.S. Xin lỗi vì bất kỳ lỗi ngôn ngữ nào, tôi không phải là tiếng Anh và tôi vẫn chưa nắm vững được ngôn ngữ đó.

Answer 1

Về cơ bản, bạn đang yêu cầu thuật toán edit distance, nhưng chỉ cho phép thao tác chuyển vị (a.k.a. swapping, twiddling). Trong cuốn sách "Giới thiệu về thuật toán", bạn sẽ tìm thấy manh mối để thực hiện thao tác twiddle, đó là một trong những vấn đề ở cuối chương về lập trình động. Ngoài ra, trong cuốn sách "Hướng dẫn thiết kế thuật toán", trong chương về lập trình động, có một cách thực hiện đầy đủ thuật toán chỉnh sửa khoảng cách trong C - sans thao tác chuyển đổi (một lần nữa, đó là một trong những bài tập được đề xuất ở cuối chương)).

Trong liên kết ở trên, bạn sẽ thấy rằng cách điển hình để thực hiện thuật toán chỉnh sửa khoảng cách là sử dụng lập trình động, có chi phí thời gian O (mn) và O (mn). Theo tôi biết, không có cách nào để làm điều đó nhanh hơn (ví dụ trong thời gian ít hơn O (mn)), nhưng chắc chắn bạn có thể làm điều đó trong không gian ít hơn - thông minh, bạn có thể giảm không gian cho O (m), được chỉ có hàng hiện tại và hai hàng trước đó trong bảng là cần thiết để tính toán chi phí của một hoạt động chuyển vị.

Tức là, bạn chỉ cần chỉnh sửa khoảng cách . Nếu bạn cần các thao tác chỉnh sửa thực tế, bạn đang bị mắc kẹt khi sử dụng không gian O (mn) để xây dựng lại giải pháp nếu sử dụng lập trình động. Tuy nhiên, bạn có thể giảm không gian thành O (min {m, n}) và tạo lại các hoạt động chỉnh sửa thực tế, bằng cách sử dụng Hirschberg's algorithm.