Исключить варианты / ротации списков в решениях SWI-Prolog - PullRequest
Новая
       27

Исключить варианты / ротации списков в решениях SWI-Prolog

1 голос
/ 13 января 2020

Я хочу исключить несколько поворотов / зеркал списка в моих решениях предиката. Я приведу пример того, что я понимаю, это повороты / зеркала списка: 

[1,2,3,4,5]
[2,3,4,5,1]
[3,4,5,1,2]
[5,4,3,2,1]

Мне нужно найти предикат, который доставляет уникальную последовательность чисел от 1 до N, в соответствии с некоторыми ограничениями. Я уже понял, как вычислить правильную последовательность, но не могу найти, как исключить все повороты и зеркала из 1 списка. Есть ли простой способ сделать это?

Редактировать:

Полный предикат. clock_round (N, Sum, Yf) находит последовательность чисел от 1 до N таким образом, чтобы ни у одного триплета соседних чисел не было суммы больше, чем Sum. 

clock_round(N,Sum,Yf) :-
   generate(1,N,Xs),
   permutation(Xs,Ys),
   nth0(0,Ys,Elem1),
   nth0(1,Ys,Elem2),
   append(Ys,[Elem1,Elem2],Ym),
   safe(Ym,Sum),
   remove_duplicates(Ym,Yf).

remove_duplicates([],[]).
remove_duplicates([H | T], List) :-    
   member(H, T),
   remove_duplicates( T, List).
remove_duplicates([H | T], [H|T1]) :- 
   \+member(H, T),
   remove_duplicates( T, T1).

% generate/3 generates list [1..N]
generate(N,N,[N]).
generate(M,N,[M|List]) :-
  M < N, M1 is M + 1,
  generate(M1,N,List).

% permutation/2
permutation([],[]).
permutation(List,[Elem|Perm]) :-
  select(Elem,List,Rest),
  permutation(Rest,Perm).

safe([],_).
safe(List,Sum) :-
   (  length(List,3),
      nth0(0,List,Elem1),
      nth0(1,List,Elem2),
      nth0(2,List,Elem3),
      Elem1 + Elem2 + Elem3 =< Sum
   ;  [_|RestList] = List,    % first to avoid redundant retries
      nth0(0,List,Elem1),
      nth0(1,List,Elem2),
      nth0(2,List,Elem3),
      Elem1 + Elem2 + Elem3 =< Sum,
      safe(RestList,Sum)
   ).

Ответы [ 2 ]

2 голосов
/ 13 января 2020

Итак, вы хотите идентифицировать определенные симметрии. На первый взгляд вам придется сравнить все возможные решения с такими. То есть, помимо оплаты стоимости генерации всех возможных решений, вы будете сравнивать их друг с другом, что обойдется вам еще квадрат решений.

С другой стороны, Подумайте об этом: вы ищете определенные сочетания чисел 1..n, и, таким образом, вы можете зафиксировать одно число в определенной позиции. Давайте зафиксируем 1 в первой позиции, это не является большим вредом, так как вы можете генерировать оставшиеся n-1 решения вращением.

И затем зеркальное отображение. Что происходит, если кто-то отражает (или переворачивает) последовательность? Другая последовательность, которая является решением, производится. Открытый вопрос сейчас, как мы можем исключить определенные решения и быть уверенными, что они появятся при отражении? Например: число после 1 больше, чем число до 1.

В конце переосмыслите то, что мы сделали: сначала были созданы все решения, и только после этого некоторые были удалены. Какая трата! Почему бы не избежать сначала создания бесполезных решений?

И даже в конце, все это можно выразить гораздо более эффективно с помощью library(clpfd). 

:- use_module(library(clpfd)).

clock_round_(N,Sum,Xs) :-
   N #=< Sum, Sum #=< 3*N -2-1,
   length(Xs, N),
   Xs = [D,E|_],
       D = 1, append(_,[L],Xs), E #> L,    % symmetry breaking
   Xs ins 1..N,
   all_different(Xs),
   append(Xs,[D,E],Ys),
   allsums(Ys, Sum).

allsums([], _).
allsums([_], _).
allsums([_,_], _).
allsums([A,B,C|Xs], S) :-
   A+B+C #=< S,
   allsums([B,C|Xs], S).

?- clock_round_(N, Sum, Xs), labeling([], [Sum|Xs]).
   N = 3, Sum = 6, Xs = [1,3,2]
;  N = 4, Sum = 9, Xs = [1,3,4,2]
;  N = 4, Sum = 9, Xs = [1,4,2,3]
;  N = 4, Sum = 9, Xs = [1,4,3,2]
;  N = 5, Sum = 10, Xs = [1,5,2,3,4]
...
0 голосов
/ 13 января 2020

Вот возможность сделать это: 

is_rotation(L1, L2) :-
   append(H1, H2, L1),
   append(H2, H1, L2).

is_mirror(L1, L2) :-
    reverse(L1,L2).

my_filter([H|Tail], [H|Out]):-
    exclude(is_rotation(H), Tail, Out_1),
    exclude(is_mirror(H), Out_1, Out).

Например 

?- L = [[1,2,3,4,5],[2,3,4,5,1],[3,4,5,1,2],[5,4,3,2,1], [1,3,2,4,5]],my_filter(L, Out).
L = [[1, 2, 3, 4, 5], [2, 3, 4, 5, 1], [3, 4, 5, 1, 2], [5, 4, 3, 2, 1], [1, 3, 2, 4|...]],
Out = [[1, 2, 3, 4, 5], [1, 3, 2, 4, 5]].
...