Перестановки на Прологе , определение, является ли четной перестановка

Доброго времени суток=)

Требуется создать предикат, который определяет четность перестановки. На вход подается два списка - один исходный, второй переставленный.

   четная_перестановка([2, 3, 4, 5, 6], [3, 4, 5, 6, 2]) - да
   четная_перестановка([2, 3, 4, 5, 6], [3, 4, 5, 2, 6]) - нет

Если я правильно поняла, чего от меня хотят, то нужно посчитать, сколько раз в списке делалась перестановка и проверить на четность это число. Перестановки формируются следующим образом:
2, 3, 4, 5, 6 // нулевая
3, 2, 4, 5, 6 // первая
3, 4, 2, 5, 6 // вторая
3, 4, 5, 2, 6 // третья
3, 4. 5, 6, 2 // четвертая

Если у кого-то есть какие-то мысли, как можно это реализовать, - подскажите, пожалуйста. А то у меня вся фантазия иссякла уже=(

I_love_coffee, я уточнить хочу задание.
за последние сутки выпила тонну болеутолящих (зубы болят) и как-то отупела.
В задании только один элемент списка может переставляться? Или это перестановка в обычном смысле и чётность перестановки в обычном смысле?

Ну, переставляются первый со вторым, второй с третьим, третий с четвертым и т.д....
Могу привести пример из методички, но там совсем уж глухо написано - пример на списке из трех элементов.

Цитирую:
"Отношение ЧЕТНАЯ_ПЕРЕСТАНОВКА для выяснения четности перестановки Y списка X. Например:
? - ЧЕТНАЯ_ПЕРЕСТАНОВКА([3, 4, 5], [4, 5, 3]) – истинно
? - ЧЕТНАЯ_ПЕРЕСТАНОВКА([3, 4, 5], [4, 3, 5]) – нет

пример фомирования перестановки:
Х = 3,4,5 -> 4,3,5 - первая перестановка
4,5,3 - вторая перестановка"

П.С.сочувствую, что зубы болят

Сообщение отредактировано: I_love_coffee - 18.12.09, 20:56

Походу в обычном смысле. То есть задаётся исходный список и любая из n! перестановок, и нужно вывести да или нет. Можно попытаться решить завтра, после визита в стоматологию.
Только я на ТурбоПрологе пишу, а у вас (судя по методичке) какой-то другой.
На Турбо пойдёт ли нет?

Мы на турбо пишем, ну или на вижуале. Да мне хоть на каком - идея-то одна=)
Спасибо, Светлана. Удачи Вам у стоматолога

Превед
Как я делала (на примерах).

1. [2,3,4] и [4,3,2]
2<3 но 4>3 -> -1
2<4 но 4>2 -> -1
3<4 но 3>2 -> -1
-1*(-1)*(-1)=-1 - перестановка нечётная

2. [2,3,4] и [4,2,3]
2<3 но 4>2 -> -1
2<4 но 4>3 -> -1
3<4 и 2<3 -> +1
-1*(-1)*(+1)=+1 - перестановка чётная

domains
list=integer*
 
predicates
p0(list,list)
even_head(integer,list,integer,list,integer)
even(list,list,integer)
inv(integer,integer,integer,integer,integer)
 
clauses
p0(L,L1):-
  even(L,L1,K),
  K=1.
 
even([],[],1).
even([H|T],[H1|T1],M):-
  even_head(H,T,H1,T1,K),
  even(T,T1,M1),
  M=M1*K.
  
even_head(X,[],A,[],1).
even_head(X,[H|T],X1,[H1|T1],P):-
  inv(X,H,X1,H1,K),
  even_head(X,T,X1,T1,P1),
  P=K*P1.
  
inv(X,H,X1,H1,1):-
  X<H,X1<H1,!.  
inv(X,H,X1,H1,-1):-
  X<H,X1>H1,!.
inv(X,H,X1,H1,1):-
  X>H,X1>H1,!.
inv(X,H,X1,H1,-1):-
  X>H,X1<H1,!.          
  
goal
 clearwindow,
 p0([2,3,4],[4,3,2]),!,write("yes");
 write("no").

Сообщение отредактировано: Swetlana - 19.12.09, 11:18

Светлана, спасибо огромное, щас буду разбираться, как там че работает=)

На самом деле не имеет значения переставляются только соседние элементы или произвольные. Любой обмен меняет четность перестановки.

Есть еще один признак четности, подсчет числа инверсий, когда два элемента (не обязательно соседние) расположены в неправильном порядке.
1 2 3 - не имеет инверсий
2 1 3 - одну инверсию (2>1)
2 3 1 - две инверсии (2>1, 3>1)
3 2 1 - три инверсии (3>2, 3>1, 2>1)

Правда не уверен, что это можно реализовать эффективнее, чем прямой подсчет перестановок.

amk, я пробовала написать именно подсчет числа инверсий, но ниче у меня не вышло=( Видимо, туго с прологовской логикой=(

Цитата amk @ 19.12.09, 13:47

Есть еще один признак четности, подсчет числа инверсий, когда два элемента (не обязательно соседние) расположены в неправильном порядке.
....
Правда не уверен, что это можно реализовать эффективнее, чем прямой подсчет перестановок.

Именно это я и реализовала в программе - подсчёт числа инверсий
И что в этом неэффективного?

Когда я писал, не обратил внимания, что речь идет о сравнении двух расстановок. А не перестановке какой-то стандартной последовательности. В том случае оба метода давали бы сложность O(n²). В данной задаче для того чтобы определить необходимый порядок элементов при сортировке нужно еще O(n), получается O(n³).
В принципе можно, используя быструю сортировку, сортировать к расстановке по возрастанию с общей сложностью O(n log n), но не знаю можно ли при этом на прологе определить число перестановок.

amk, не поняла, почему O(n³).
У меня есть 2 расстановки. Я определяю количество инверсий второй расстановки относительно первой.
Для этого я сравниваю порядок пары элементов первой расстановки и порядок соответствующей пары второй.
На Паскале для перебора всех пар я бы написала двойной цикл. В Прологе вместо цикла рекурсия, т.е. двойная рекурсия. В смысле из каждой точки внешней рекурсии вызывается ещё одна рекурсия.
Всё те же O(n²) получается.

Цитата

не знаю можно ли при этом на прологе определить число перестановок.

На Прологе можно всё. Даже сортировку "пузырёк" написать с помощью рекурсии. Только она немного неестественно будет выглядеть.

Сообщение отредактировано: Swetlana - 20.12.09, 17:04

Ты просто синхронно перебираешь пары, проверяя одинаковый ли у них порядок, для этого действительно достаточно O(n²). А я говорил про пересортировку одной из последовательностей, чтобы она соответствовала другой. Там добавляется еще одна пробежка по цепочке, чтобы определить нужный порядок.

Насчет возможности всего. Пролог, насколько я знаю, использует списковую структуру данных. Быстрая сортировка Хоара там неприменима. Вместо нее используются сортировки типа расщепить/сцепить. А в них непонятно как считать перестановки. По крайней мере так с ходу.

Быстрая сортировка.
выбрать элемент, называемый опорным.
сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
повторить рекурсивно для «меньших» и «больших».

domains
list=integer*
 
predicates
supersort(list,list)
div(integer,list,list,list)
conc(list,list,list)
 
clauses
 supersort([],[]).
 supersort([H|T],L):-
         div(H,T,Small,Big),
         supersort(Small,Small_sort),
         supersort(Big,Big_sort),
         conc(Small_sort,[H|Big_sort],L).
 
 div(_,[],[],[]).
 div(H,[X|T],[X|Small],Big):-
                           H > X,!,  
                           div(H,T,Small,Big).
 div(H,[X|T],Small,[X|Big]):-
                           div(H,T,Small,Big).
 
 conc([],L,L).
 conc([H|T],L2,[H|L]):-
                     conc(T,L2,L).      
 
 goal
  supersort([1,7,5,1,9,3],L),write(L),nl.

Программа быстрой сортировки будет работать очень неэффективно, если один из списков Big и Small существенно длиннее другого. Это произойдет, например, в случае, когда список почти отсортирован. От этого недостатка можно избавиться следующим образом: разбивать список на два списка примерно одинаковой длины.

domains
list=integer*
 
predicates
supersort2(list,list)      
div2(list,list,list)  
concsort(list,list,list)
  
clauses
 supersort2([],[]).
 supersort2([X],[X]).
 supersort2(L,S):-
         div2(L,L1,L2),
         supersort2(L1,S1),
         supersort2(L2,S2),
         concsort(S1,S2,S).
 
 div2([],[],[]).
 div2([X],[X],[]).
 div2([X,Y|L],[X|L1],[Y|L2]):-
                      div2(L,L1,L2).
 
 concsort([],L,L).
 concsort(L,[],L).
 concsort([H1|T1],[H2|T2],[H1|T]):-
                      H1<=H2,!,
                      concsort(T1,[H2|T2],T).
 concsort([H1|T1],[H2|T2],[H2|T]):-                      
                      concsort([H1|T1],T2,T).                    
 
 goal
  supersort2([1,7,95,4,9,3],L),write(L),nl.

Swetlana, почти точно как первая программу я составил, когда изучал когда-то пролог (отличия в основном в оформлении, у тебя кажется Turbo-Prolog, я пользовался каким-то другим, там программа не делилась на разделы). Пользоваться им правда потом почти не пришлось, поэтому многое забылось.

Я про то написал, что без специального (и подозреваю довольно сложного) анализа неясно, как в результате этой быстрой сортировки поменялась четность перестановки.