ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Rustam Ramazanov                     2:5020/400     09 Jan 2003  19:39:12
 To : Gennady Mayko
 Subject : Re: число инверсий в перестанове
 -------------------------------------------------------------------------------- 
 

 Приветствую!
 
 GM> Каким образом можно узнать число инверсий в
 GM> заданной перестановке, чтобы
 GM> определить, четная эта перестановка или нечетная?
 
 GM> Я знаю (и использую сейчас) способ, основанный на
 GM> прямом подсчете инверсий пар
 GM> чисел в перестановке, но мне он кажется неэффективным.
 
 Можно попробовать так:
 Разбить перестановку в произведение циклов (транспозиция - цикл длиной 
 2). Делается это в лоб, только надо отслеживать уже задействованные 
 элементы. Далее посчитать кол-во циклов у которых длина четная. Если их 
 четное кол-во, то и перестановка четная, если нечетное - перестановка 
 тоже нечетная.
 Возможно это будет реализовать проще, чем подсчет инверсий. 
 
 Рустам.
 -- 
 Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
 --- ifmail v.2.15dev5
  * Origin: Talk.ru (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    число инверсий в перестанове   Gennady Mayko   07 Jan 2003 13:03:49   число инверсий в перестанове   Konstantin Azarov   07 Jan 2003 15:50:39   Re: число инверсий в перестанове   Rustam Ramazanov   09 Jan 2003 19:39:12