chuỗi thuật toán chuyển vị

Question

Giả sử có được đưa ra hai String:

String s1= "MARTHA" 
String s2= "MARHTA" 

ở đây chúng tôi trao đổi vị trí của T và H. Tôi quan tâm đến viết mã mà đếm có bao nhiêu thay đổi này là cần thiết để chuyển đổi từ một String để Chuỗi khác .

Answer 1

Giả sử rằng số lượng khoảng cách chỉ hoán đổi, đây là ý tưởng dựa trên hoán vị, chạy theo thời gian tuyến tính.

Bước đầu tiên của thuật toán là đảm bảo rằng hai chuỗi thực sự tương đương với nội dung ký tự của chúng. Điều này có thể được thực hiện trong thời gian tuyến tính bằng cách sử dụng một bảng băm (hoặc một mảng cố định bao gồm tất cả các bảng chữ cái). Nếu không, thì s2 không thể được coi là hoán vị của s1, và "số lượng trao đổi" là không liên quan.

Bước thứ hai tính số lượng hoán đổi tối thiểu cần thiết để chuyển đổi s2 thành s1. Điều này có thể được thực hiện bằng cách kiểm tra p hoán vị tương ứng với phép biến đổi từ s1 đến s2. Ví dụ: nếu s1 = "abcde" và s2 = "badce", sau đó p = (2,1,4,3,5), nghĩa là vị trí 1 chứa phần tử # 2, vị trí 2 chứa phần tử số 1, v.v ... hoán vị có thể được chia thành permutation cycles trong thời gian tuyến tính. Các chu kỳ trong ví dụ là (2,1) (4,3) và (5). Số hoán đổi tối thiểu là tổng số các hoán đổi được yêu cầu cho mỗi chu kỳ. Chu kỳ độ dài k yêu cầu hoán đổi k-1 để "sửa lỗi". Do đó, Số lượng hoán đổi là N-C, trong đó N là độ dài chuỗi và C là số chu kỳ. Trong ví dụ của chúng tôi, kết quả là 2 (hoán đổi 1,2 và sau đó là 3,4).

Giờ đây, có hai vấn đề ở đây, và tôi nghĩ rằng tôi quá mệt mỏi để giải quyết chúng ngay bây giờ :)

1) Giải pháp của tôi giả định rằng không có nhân vật được lặp lại, mà không phải là luôn luôn như vậy. Cần có một số điều chỉnh để tính chính xác số lần hoán đổi.

2) Công thức của tôi # MinSwaps = N-C cần bằng chứng ... Tôi không tìm thấy nó trên web.

Answer 2

Có một số thuật toán edit distance, liên kết Wikipeida đã cho có liên kết đến một vài.

Answer 3

Vấn đề của bạn không dễ dàng như vậy, vì trước khi tính toán các giao dịch hoán đổi bạn cần đảm bảo rằng mọi giao dịch hoán đổi sẽ làm giảm "khoảng cách" (bằng nhau) giữa hai chuỗi này. Sau đó, thực sự bạn tìm số nhưng bạn nên tìm số lượng nhỏ nhất (hoặc ít nhất tôi giả sử), nếu không có tồn tại cách vô hạn để trao đổi một chuỗi để có được một số khác.

Trước tiên, bạn nên kiểm tra xem những ký tự nào đã được đặt sẵn, sau đó cho mọi ký tự không nhìn nếu có một cặp có thể hoán đổi để khoảng cách tiếp theo giữa các chuỗi bị giảm. Sau đó lặp lại cho đến khi bạn hoàn thành quá trình.

Nếu bạn không muốn thực hiện điều đó một cách hiệu quả nhưng chỉ cần đếm số lượng hoán đổi sử dụng một mảng bit trong đó bạn có 1 cho mỗi ký tự được đặt và 0 nếu không. Bạn sẽ kết thúc khi mỗi bit là 1.