Tạo tất cả các hoán vị của danh sách [1, 1, 2, 2, ..., n, n], nơi số lượng phần tử giữa mỗi cặp thậm chí là trong Prolog

Question

Gần đây tôi đã bắt đầu học Prolog và tôi có một nhiệm vụ để viết một vị list(N, L) mà tạo ra danh sách L sao cho:

• L có chiều dài 2N,
• mỗi số từ 1 đến N xảy ra chính xác hai lần trong L,
• giữa mỗi cặp của cùng một nguyên tố có một thậm chí số lượng các phần tử khác,
• lần xuất hiện đầu tiên của mỗi số đang tăng dần er.

Tác giả nói rằng có N! danh sách như vậy.

Ví dụ, đối với N = 3 tất cả các giải pháp bao gồm:

?- list(3, L). 
L = [1, 1, 2, 2, 3, 3] ; 
L = [1, 1, 2, 3, 3, 2] ; 
L = [1, 2, 2, 1, 3, 3] ; 
L = [1, 2, 2, 3, 3, 1] ; 
L = [1, 2, 3, 3, 2, 1] ; 
L = [1, 2, 3, 1, 2, 3] ; 
false. 

giải pháp hiện tại của tôi trông giống như:

even_distance(H, [H | _]) :- 
    !. 
even_distance(V, [_, _ | T]) :- 
    even_distance(V, T). 

list(N, [], _, Length, _, _) :- 
    Length =:= 2*N, 
    !. 
list(N, [New | L], Max, Length, Used, Duplicates) :- 
    select(New, Duplicates, NewDuplicates), 
    even_distance(New, Used), 
    NewLength is Length + 1, 
    list(N, L, Max, NewLength, [New | Used], NewDuplicates). 
list(N, [New | L], Max, Length, Used, Duplicates) :- 
    Max < N, 
    New is Max + 1, 
    NewLength is Length + 1, 
    list(N, L, New, NewLength, [New | Used], [New | Duplicates]). 

list(N, L) :- 
    list(N, L, 0, 0, [], []). 

Nó hai điều:

• nếu tối đa hiện nay là nhỏ hơn N, thêm số đó vào danh sách, đặt nó vào danh sách các bản sao và cập nhật giá trị tối đa;
• chọn một số trùng lặp, kiểm tra xem có số phần tử giữa số đó và số đã có trong danh sách hay không (nghĩa là số đó ở vị trí lẻ), sau đó thêm số đó vào danh sách và xóa nó khỏi trùng lặp.

Nó hoạt động, nhưng nó rất chậm và trông không đẹp lắm.

Tác giả của bài tập này cho thấy rằng đối với N < 12, giải pháp của ông tạo ra một danh sách duy nhất với ~ 11 suy luận (sử dụng time/1 và chia kết quả bằng N!). Với giải pháp của tôi nó phát triển đến ~ 60.

Tôi có hai câu hỏi:

1. Làm thế nào để cải thiện thuật toán này?
2. Sự cố này có thể được khái quát hóa với một số ứng dụng đã biết khác không? Tôi biết về các vấn đề tương tự dựa trên multiset [1, 1, 2, 2, ..., n, n] (ví dụ như ghép nối Langford), nhưng không thể tìm thấy một cái gì đó như thế này.

Tôi hỏi vì vấn đề ban đầu là liệt kê các giao lộ trong đường cong khép kín tự giao nhau. Bạn vẽ đường cong như vậy, chọn một điểm và hướng và đi theo đường cong, liệt kê từng giao lộ khi gặp lần đầu tiên và lặp lại số trong cuộc họp thứ hai: example (với câu trả lời [1, 2, 3, 4, 5, 3, 6, 7, 8, 1, 9, 5, 4, 6, 7, 9, 2, 8]).

Tác giả tuyên bố rằng mọi đường cong như vậy đều thỏa mãn vị từ list, nhưng không phải mọi danh sách đều tương ứng với một đường cong.

Answer 1

Tôi đã phải sử dụng số học để đáp ứng yêu cầu về các cặp số nguyên được phân tách bằng số lượng phần tử. Sẽ được tốt đẹp để có thể giải quyết mà không có số học ở tất cả ...

 

list(N,L) :- numlist (1,N,H), list_(H,L), even_(L). 

list_([D|Ds],[D|Rs]) :- 
    list_(Ds,Ts), 
    select (D,Rs,Ts). 
list_([],[]). 

even_(L) :- 
    forall(nth0(P,L,X), (nth0(Q,L,X), abs(P-Q) mod 2 =:= 1)). 

chọn/3 được sử dụng trong 'chế độ chèn'.

chỉnh sửa để tránh số học, chúng ta có thể sử dụng sơ đồ này tiết hơn

even_(L) :- 
    maplist(even_(L),L). 
even_(L,E) :- 
    append(_,[E|R],L), 
    even_p(E,R). 
even_p(E,[E|_]). 
even_p(E,[_,_|R]) :- even_p(E,R). 

chỉnh sửa

Dưới đây là một đoạn dựa trên phân công trong một danh sách được xây dựng sẵn của 'khe' trống. Dựa trên thử nghiệm của tôi, nó nhanh hơn giải pháp của bạn - khoảng 2 lần.

list(N,L) :- 
    N2 is N*2, 
    length(L,N2), 
    numlist(1,N,Ns), 
    pairs(Ns,L). 

pairs([N|Ns],L) :- first(N,L,R),even_offset(N,R),pairs(Ns,L). 
pairs([],_). 

first(N,[N|R],R) :- !. 
first(N,[_|R],S) :- first(N,R,S). 

even_offset(N,[N|_]). 
even_offset(N,[_,_|R]) :- even_offset(N,R). 

nỗ lực đầu tiên của tôi, lọc với even_/1 sau mỗi chèn, đã chậm hơn nhiều. Ban đầu tôi đã tập trung vào việc đẩy bộ lọc ngay sau khi lựa chọn/3, và hiệu suất thực sự gần như tốt như đoạn cuối, nhưng than ôi, nó mất một giải pháp trong số 6 ...