пятница, 4 февраля 2011 г.

Перестановки (permutations)

Количество перестановок без повторений: N!
Количество перестановок с повторениями: N!/(k1!*k2!*..*kn!),
где N-общее количество элементов, ki – количество вхождений i-ого элемента

0. Понятие перестановки. Разложение на циклы + [Video]   
    Практика: [Обратная перестановка]
             
[Степень перестановки]
             
[Восстановление перестановки]

1. Знак перестановки. Подсчет количества инверсий.
    Практика:[In the Army Now(timus 1090)] merge sort + [Video]
            
[In the Army Now(timus 1090)] bucket search + [Video]
            
[In the Army Now(timus 1090)] fenwic tree + [Video]

2. Генерация перестановок без повторений(Episode 1, Episode2).

Episode 1
    2.1. Рекурсивный способ генерации всех перестановок в лексикографическом порядке.
        Практика:
[Меньшиков 2B]
    2.2. Рекурсивный способ генерации всех перестановок в антилексикографическом порядке.
        Практика:
[Меньшиков 2B]

Episode 2
    2.3. Генерация следующей перестановки в лексикографическом порядке.
        Практика:
[Меньшиков 2B]
    2.4. Генерация всех перестановок с помощью транспозиции двух соседних элементов.
        Практика:
[Меньшиков 2B]

3. Генерация перестановок с повторениями.
    3.1. Рекурсивный способ генерации всех перестановок в лексикографическом порядке.
        Практика:
[Меньшиков 3B]
    3.2. Генерация следующей перестановки в лексикографическом порядке.
        Практика:
[Меньшиков 3B]
    3.3. Генерация предыдущей перестановки в лексикографическом порядке.
        Практика:
[Меньшиков 3B]

4. Генерация перестановки по номеру и получение номера по перестановке.
    4.1. Генерация перестановки по номеру.
        Практика:
[Перестановка по номеру]
    4.2. Получения номера по перестановке
        Практика:
[Перестановка по номеру]

5. Буквометика
    Практика: [Футбол и математика]

Комментариев нет:

Отправить комментарий