Generowanie wszystkich permutacji z listy [1, 1, 2, 2, ..., n, n] gdzie liczba elementów między każdą parą jest nawet w Prologu

Question

Niedawno zacząłem uczyć się Prologa i dostałem zadanie do napisania predykatem list(N, L) że generuje listy L takie, że:

• L ma długość 2N
• każdą liczbę pomiędzy 1 i N następuje dokładnie dwukrotnie L
• pomiędzy każdą parą samego pierwiastka jest równy liczba innych elementów,
• pierwsze wystąpienia każdej liczby rosną w porządku er.

Autor oświadcza, że ​​istnieje N! takie listy.

Na przykład dla n = 3 wszystkie rozwiązania są:

?- 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. 

Moje obecne rozwiązanie wygląda następująco:

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, [], []). 

Robi dwie rzeczy:

• jeśli prąd maksymalny to mniej niż N, dodaj ten numer do listy, umieść go na liście duplikatów i zaktualizuj max;
• wybierz trochę duplikatu, sprawdź, czy między nim a parzystą liczbą elementów znajduje się liczba (np. Numer jest na pozycji nieparzystej), a następnie dodaj go do listy i usuń z duplikatów.

Działa, ale działa wolno i nie wygląda ładnie.

Autor tego ćwiczenia pokazuje, że dla N < 12 jego rozwiązanie generuje pojedynczą listę ze średnio ~ 11 wnioskami (używając time/1 i dzieląc wynik przez N!). Dzięki mojemu rozwiązaniu wzrasta do ~ 60.

Mam dwa pytania:

1. Jak poprawić ten algorytm?
2. Czy ten problem można uogólnić na inny znany? Wiem o podobnych problemach opartych na multisetach [1, 1, 2, 2, ..., n, n] (np. Parowanie Langford), ale nie mogłem znaleźć czegoś takiego.

Pytam, ponieważ pierwotny problem polega na wyliczaniu przecięć w przecinającej się zamkniętej krzywej. Narysujesz taką krzywą, wybierasz punkt i kierunek i podążasz za krzywą, wyliczając każde przecięcie po pierwszym spotkaniu i powtarzając numer na drugim spotkaniu: example (z odpowiedzią [1, 2, 3, 4, 5, 3, 6, 7, 8, 1, 9, 5, 4, 6, 7, 9, 2, 8]).

Autor stwierdza, że ​​każda taka krzywa spełnia predykat list, ale nie każda lista odpowiada krzywej.

Answer 1

Musiałem uciec się do arytmetyki, aby spełnić warunek dotyczący par liczb całkowitych oddzielonych nawet liczbą elementów. Byłoby miło móc rozwiązać bez arytmetycznych ...

 

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)). 

Opcja select/3 jest używana w "trybie wstawiania".

edit aby uniknąć arytmetyki, możemy skorzystać z tej dokładniejszych informacji schematu

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). 

edycji

Oto fragment na podstawie cesji w Montowane listy pustych „gniazdach”. Opierając się na moim teście, jest szybszy niż twoje rozwiązanie - około 2 razy.

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). 

Moja pierwsza próba, filtrowanie even_/1 po każdym włożeniu, był znacznie wolniejszy. Początkowo koncentrowałem się na przesuwaniu filtra zaraz po selekcji/3, a wydajność była prawie całkiem dobra jako ostatni fragment, ale niestety, traci rozwiązanie z 6 ...