OCaml chèn một phần tử vào danh sách

Question

Cách tiêu chuẩn chèn phần tử vào một vị trí cụ thể trong danh sách trong OCaml là gì. Chỉ cho phép đệ quy. Không cho phép thao tác gán.

Mục tiêu của tôi là nén biểu đồ trong ocaml bằng cách xóa các đỉnh bằng in_degree = out_degree = 1. Vì lý do này, tôi cần phải loại bỏ các cạnh liền kề để tạo một cạnh duy nhất. Bây giờ các cạnh nằm trong một danh sách [(6,7); (1,2); (2,3); (5,4)]. Vì vậy, tôi cần phải loại bỏ các cạnh đó khỏi danh sách và thêm một cạnh. vì vậy danh sách trên sẽ trông giống như [(6,7); (1,3); (5,4)]. Ở đây chúng ta thấy (1,2), (2,3) được lấy ra và (1,3) được chèn vào vị trí thứ hai. Tôi đã nghĩ ra một thuật toán cho điều này. Nhưng để làm điều này tôi cần biết làm thế nào tôi có thể loại bỏ các cạnh (1,2), (2,3) từ vị trí 2,3 và chèn (1,3) ở vị trí 2 mà không có bất kỳ biến rõ ràng và một cách đệ quy.

Answer 1

danh sách OCaml là bất biến vì vậy không có điều đó giống như loại bỏ và chèn các yếu tố trong hoạt động danh sách.

Việc bạn có thể làm là tạo danh sách mới bằng cách sử dụng lại một phần nhất định của danh sách cũ. Ví dụ: để tạo danh sách (1, 3)::xs' từ (1, 2)::(2, 3)::xs', bạn thực sự sử dụng lại xs' và tạo danh sách mới bằng cách sử dụng hàm tạo cons.

Và kiểu kết hợp rất thuận tiện khi sử dụng:

let rec transform xs =            
    match xs with 
    | [] | [_] -> xs 
    | (x, y1)::(y2, z)::xs' when y1 = y2 -> (x, z)::transform xs' 
    | (x, y1)::(y2, z)::xs' -> (x, y1)::transform ((y2, z)::xs') 

Answer 2

Bạn có thể làm một cái gì đó như thế:

let rec compress l = match l with            
    [] -> []               
| x :: [] -> [x]              
| x1 :: x2 :: xs -> 
    if snd x1 = fst x2 then 
    (fst x1, snd x2) :: compress xs 
    else x1 :: compress (x2 :: xs) 

Answer 3

Bạn đang sử dụng datastructure sai để lưu trữ các cạnh của bạn và doesnt câu hỏi của bạn biết rằng bạn không thể chọn một datastructure khác nhau. Như các áp phích khác đã nói: danh sách là bất biến nên việc xóa lặp đi lặp lại các yếu tố sâu bên trong chúng là một hoạt động tương đối tốn kém (O (n)).

Tôi cũng không hiểu tại sao bạn phải lắp lại cạnh mới ở vị trí 2. Biểu đồ được xác định bởi G = (V, E) trong đó V và E là đặt của đỉnh và cạnh. Thứ tự của chúng không có vấn đề gì. Định nghĩa về đồ thị này cũng đã cho bạn biết một cơ sở hạ tầng tốt hơn cho các cạnh của bạn: bộ.

Trong ocaml, các bộ được thể hiện bằng các cây nhị phân cân bằng để độ phức tạp trung bình của việc chèn và xóa các thành viên là O (log n). Vì vậy, bạn thấy rằng để xóa các thành viên phức tạp này chắc chắn là tốt hơn so với một trong các danh sách (O (n)) mặt khác là tốn kém hơn để thêm các thành viên vào một bộ hơn là để thêm các yếu tố vào một danh sách bằng cách sử dụng các khuyết điểm hoạt động.

Một cơ sở hạ tầng thay thế sẽ là một hashtable khi chèn và xóa có thể được thực hiện trong thời gian O (1). Hãy để các phím trong hashtable được các cạnh của bạn và vì bạn không sử dụng các giá trị, chỉ cần sử dụng một hằng số như đơn vị hoặc 0.