Tôi muốn có một loại quy nạp để mô tả hoán vị và hành động của chúng trên một số vật chứa. Rõ ràng là tùy thuộc vào mô tả loại này độ phức tạp của định nghĩa (về độ dài của nó) của thuật toán (thành phần tính toán hoặc nghịch đảo, phân hủy thành các chu kỳ rời rạc, vv) sẽ khác nhau.Trên đại diện của hoán vị
Hãy xem xét định nghĩa sau trong Coq. Tôi tin rằng nó được chính thức hoá mã Lehmer:
Inductive Permutation : nat -> Set :=
| nil : Permutation 0
| cons : forall (n k : nat), Permutation (k + n) -> Permutation (k + S n).
Nó rất dễ dàng để xác định hành động của nó đối với vectơ kích thước n, hơi khó vào container khác và (ít nhất là đối với tôi) khó có thể tìm ra chính thức hóa thành phần hoặc nghịch đảo.
Hoặc chúng ta có thể biểu diễn hoán vị như một bản đồ hữu hạn với các thuộc tính. Thành phần hoặc nghịch đảo có thể dễ dàng xác định nhưng phân hủy nó thành các chu kỳ rời nhau là khó khăn.
Vì vậy, câu hỏi của tôi là: có bất kỳ giấy tờ nào giải quyết vấn đề thương mại này không? Tất cả các công trình, mà tôi đã tìm thấy, đối phó với độ phức tạp tính toán trong các thiết lập bắt buộc, trong khi tôi quan tâm đến "sự phức tạp về lý luận" và lập trình hàm.
Tôi không biết gì về Coq, nhưng việc này có giúp ích gì không? http://coq.inria.fr/stdlib/Coq.Sorting.Permutation.html –
Thật không may, nó không. Những gì tôi muốn là mã hóa hoán vị mà không cần tham chiếu đến một container. Mặc dù nó sẽ là dễ chịu để có một định nghĩa container-chung của mối quan hệ tương tự như một trong những đề cập. –
Có lẽ bạn có thể chuyên nó để nó permutes một danh sách được sắp xếp các chỉ số? –