Понятие перестановки имеет множество применений в информатике, например, в анализе алгоритмов сортировки и в реализации распределенных систем.Формально перестановка - это биекция из множества на себя.Для простоты ограничимся множествами [n]: = {1, 2,.,,, n} из первых n натуральных чисел и обозначим через Sn множество всех перестановок на [n].Часто удобно представлять перестановку σ набором n (σ (1), σ (2), ..., σ (n)).Обмен двух элементов перестановки приводит к другой перестановке.Для i, j ∈ [n], пусть Tij: Sn → Sn - отображение, которое меняет местами образы i и j, то есть если σ ∈ Sn, то τ: = Tij (σ) задается как τ (i) =σ (j), τ (j) = σ (i) и τ (k) = σ (k), если i 6 = k 6 = j.Пример.Пусть σ = (2, 4, 3, 1).Тогда T13 (σ) = (3, 4, 2, 1).Теперь рассмотрим возможность обмена только с некоторыми парами (i, j).Для любого целого числа d ≥ 0 пусть
Pd: = {(i, j) ∈ [n] × [n]: i = j или d ≤ j - i ≤ n - d}
Скажите, что перестановка τ равна (d, )-reachable from σ if there are (i1, j1),(i2, j2), . . . ,(i, j ) ∈ Pd such that the corresponding swaps transform σ to τ , that is, τ = Ti j` ◦ · · · ◦ Ti2j2 ◦ Ti1j1 (σ).
ЗАДАЧА:
Докажите, что для любого натурального числа n перестановка (n, n - 1, ..., 1) равна (1, bn / 2c) - достижимо из (1, 2, ..., n).
Чтобы выяснить, является ли τ (d, )-reachable from σ, one may apply bidirected search as follows: First generate all permutations that are (d, b / 2c) -достижимым из σ. Затем сгенерируем все перестановки, которые (d, d` / 2e) -достижимы из τ.Наконец, сообщите «ДА», если два сгенерированных набора пересекаются, и в противном случае сообщите «НЕТ». Опишите алгоритм с использованием псевдокода, в частности, опишите, как генерируются наборы перестановок (вы можете считать, что данные аргументы действительны:не реализовывать обработку ошибок.)
Реализовать алгоритм предыдущей задачи с использованием языка программирования Java. Покажите свой код. Используйте свою реализацию для решения для всех d = 1, 2, ..., 4 и = 1, 2, . . . , 9, whether (9, 8, . . . , 1) is (d,) - достижимы из (1, 2,.,,9).Показать результаты в виде матрицы 4 × 9.