@Новенький

Уважаемые эксперты помогите решить задачки по перестановкам...
№1
Степень перестановки
(Время: 1 сек. Память: 16 Мб)
Требуется вычислить степень заданной перестановки.
Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Количество различных перестановок порядка N равно PN = N!
Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говорит, что на i место нужно поставить ai элемент множества, где ai - i-тый элемент перестановки.
Обратной перестановкой к перестановке π называется такая перестановка π-1, что ππ-1 = π-1π = ε, где ε – тождественная перестановка.

Степенью перестановки называется минимальное натуральное число k такое, что πk = ε

Входные данные
В первой строке входного файла INPUT.TXT записано число 0 < N <= 100 - порядок перестановки. Во второй строке записана сама перестановка.

Выходные данные
В выходной файл OUTPUT.TXT выведите степень данной перестановки. Гарантируется, что ответ не превышает 10^9.

INPUT.TXT OUTPUT.TXT
3
2 3 1 3

№2
Восстановление перестановки
(Время: 1 сек. Память: 16 Мб)
Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N.
Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говорит, что на i место нужно поставить ai элемент множества, где ai - i-тый элемент перестановки.
Пусть дана перестановка π. Обозначим φ[i] - количество таких j, что π[j] > π[i], а j < i. φ называется таблицей инверсий перестановки π.
Требуется по данной таблице инверсий восстановить перестановку.

Входные данные
В первой строке входного файла INPUT.TXT записано число 0 < N <= 2000 - порядок перестановки. Во второй строке записана таблица инверсий.

Выходные данные
В выходной файл OUTPUT.TXT выведите искомую перестановку.
INPUT.TXT OUTPUT.TXT
1 3
0 0 2 2 3 1

№3
Перестановка по номеру
(Время: 1 сек. Память: 16 Мб)
Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Количество всех перестановок порядка N равно PN = N!
Требуется найти перестановку по ее номеру в лексикографическом порядке (по алфавиту). Например, для N=3 лексикографический порядок перестановок выглядит следующим образом:
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
Таким образом, перестановка (2,3,1) имеет номер 4 в этой последовательности.

Входные данные
В первой строке входного файла INPUT.TXT записано число N (1 <= N <= 12) - количество элементов в перестановке, во второй - число K (1 <= K <= N!) - номер перестановки.

Выходные данные
В выходной файл OUTPUT.TXT выведите через пробел N чисел - искомую перестановку.

Примеры
INPUT.TXT OUTPUT.TXT
1
1 1
INPUT.TXT OUTPUT.TXT
3
2 1 3 2



№4
Следующая перестановка ...
(Время: 1 сек. Память: 16 Мб)
Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N.
Найдите по заданной перестановке следующую в лексикографическом порядке (будем считать, что за перестановкой (N, N-1, ... , 3, 2, 1) следует тождественная перестановка, то есть (1, 2, 3, ... , N)).

Входные данные
В первой строке входного файла INPUT.TXT содержится число N (1 <= N <= 10^4). Во второй строке содержится перестановка (последовательность натуральных чисел от 1 до N, разделенных пробелами).

Выходные данные
Выходной файл OUTPUT.TXT должен содержать искомую перестановку.
Примеры
INPUT.TXT OUTPUT.TXT
1
1 1
INPUT.TXT OUTPUT.TXT
5
2 4 5 3 1 2 5 1 3 4

Добавлено через 32 минуты 37 секунд
Никто что ли комбинаторику не знает????

Добавлено через 32 секунды
Как и я....ыы

Вернуться к обсуждению:
Комбинаторика... Перестановки... C++

0