Re: число инверсий в перестанове

From

Rustam Ramazanov ()

To

Gennady Mayko

Date

2003-01-09T18:39:12Z

Area

RU.ALGORITHMS

From: Rustam Ramazanov <ramazanoff@univer.kharkov.ua>

Приветствую!

GM> Каким образом можно узнать число инверсий в
GM> заданной перестановке, чтобы
GM> определить, четная эта перестановка или нечетная?

GM> Я знаю (и использую сейчас) способ, основанный на
GM> прямом подсчете инверсий пар
GM> чисел в перестановке, но мне он кажется неэффективным.
Можно попробовать так:
Разбить перестановку в произведение циклов (транспозиция - цикл длиной 
2). Делается это в лоб, только надо отслеживать уже задействованные 
элементы. Далее посчитать кол-во циклов у которых длина четная. Если их 
четное кол-во, то и перестановка четная, если нечетное - перестановка 
тоже нечетная.
Возможно это будет реализовать проще, чем подсчет инверсий. 

Рустам.
-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.ru (2:5020/400)