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

Question

Существует вопрос в Art of prolog 2nd edition, где вы должны определить предикат even_permutation (Xs, Ys) и аналогично нечетные перестановки, которые при запросе, например, even_permutation ([1,2,3], [2, 3,1]) и odd_permutation ([1,2,3], [2,1,3]) имеют значение true. Эти предикаты должны иметь возможность работать со случайным списком и определять, находится ли перестановка этого списка внечетная или четная позиция.У меня есть мой предикат для перестановки, как показано.

permutation([],[]).
permutation(Xs,[Z|Zs]):-select(Z,Xs,Ys), permutation(Ys,Zs).
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]):- select(X,Ys,Zs).

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

Answer 1

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

Проблема в книге спрашивает:

Написание программ для even_permutation(Xs, Ys) и odd_permutation(Xs, Ys) , которые находят Ys, четную и нечетную перестановки списка Xs соответственно.Например, even_permutation([1,2,3], [2,3,1]) и odd_permutation([1,2,3], [2,1,3]) имеют значение true.

Таким образом, он запрашивает генераторы перестановок, а не только верификаторы.@hardmath предоставил ссылку на правильное определение четной или нечетной перестановки.Авторы книги привели два простых примера для иллюстрации.

Для меня ключом было выяснение рекурсивного определения четной или нечетной перестановки.Для всех перестановок в классическом генераторе перестановок в Прологе используется следующее понятие:

• Каждая перестановка из N + 1 элементов - это список, представляющий перестановку из N элементов с (N + 1) -ымэлемент, вставленный в список.

Предикат select или insert используется для вставки.

Для четных и нечетных перестановок я рассмотрел аналогичную идею:

• Каждая четная перестановка N + 1 элементов представляет собой либо список, представляющий четную перестановку N элементов с (N + 1)) st элемент, вставленный в нечетное положение в списке, или список, представляющий нечетное перестановку N элементов с (N + 1) st элементом, вставленным в четная позиция в списке.

• Каждая нечетная перестановка из N + 1 элементов является либо списком, представляющим нечетную перестановкуиз N элементов с (N + 1) -м элементом, вставленным в odd позиция в списке или список, представляющий четную перестановку N элементов с (N + 1) -ым элементом, вставленным в четную позицию в списке.

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

Если я добавлю к этому правило, что пустой список - это его собственная четная перестановка, то я могу определитьследующие предикаты для генерации четных и нечетных перестановок:

even_permutation( [], [] ).
even_permutation( [X|T], Perm ) :-
    even_permutation( T, Perm1 ),
    insert_odd( X, Perm1, Perm ).
even_permutation( [X|T], Perm ) :-
    odd_permutation( T, Perm1 ),
    insert_even( X, Perm1, Perm ).

odd_permutation( [X|T], Perm ) :-
    odd_permutation( T, Perm1 ),
    insert_odd( X, Perm1, Perm ).
odd_permutation( [X|T], Perm ) :-
    even_permutation( T, Perm1 ),
    insert_even( X, Perm1, Perm ).

insert_odd( X, InList, [X|InList] ).
insert_odd( X, [Y,Z|InList], [Y,Z|OutList] ) :-
    insert_odd( X, InList, OutList ).

insert_even( X, [Y|InList], [Y,X|InList] ).
insert_even( X, [Y,Z|InList], [Y,Z|OutList] ) :-
    insert_even( X, InList, OutList ).

Answer 2

Это высокоуровневое описание того, как определить, является ли перестановка четной или нечетной, в обычном смысле терминов .

. Преобразовать перестановку в произведение непересекающихся циклов.,Четность перестановки является суммой четностей ее факторов (четные времена четные или нечетные времена нечетные четные, нечетные времена четные или четные нечетные времена нечетные).Цикл нечетной длины - четная перестановка, а цикл четной длины - нечетная перестановка.Например, цикл длины один - это тождественная перестановка и, следовательно, (выраженный как пустой продукт транспозиций) - четная перестановка.

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

Другие подходы к определению четности данной перестановки описаны в статье, приведенной выше.Если вы действительно хотите перечислять только четные перестановки (или только нечетные перестановки), один из подходов состоит в том, чтобы модифицировать перечисление всех перестановок таким образом, чтобы возвращались только перестановки одинаковой четности (см. Этот раздел иодин следующий).