Реализация генерации всех циклических перестановок чисел от 1 до n.
Циклические перестановки чисел от 1 до n - такие перестановки чисел от 1 до n, при которых значение текущего числа соотносится с его текущей порядковой позицией таким образом, что она равна числу, стоявшему на позиции, с которой был осуществлён переход на текущую позицию, и при которых такие переходы можно совершать сколько угодно раз без изменения порядка расположения чисел.
Пример.
n = 3.
Изначально последовательность инициализируется, как 1 2 3.
Тогда все циклические перестановки от 1 до 3:
- 2 3 1
- 3 1 2
Перестановка 2 3 1 является циклической по следующей причине. Рассмотрение начинается с первой позиции. На ней находится число 2. Поэтому далее следует переход к позиции 2, на которой стоит число 3. Следовательно, происходит переход к позиции 3. На третей позиции расположено число 1, что означает переход к первой позиции. Таким образом, цикл замкнулся, и, если переходы продолжать, то каждая итерация будет одинакова и число проходов по перестановке будет неограниченно (Рисунок 1). Аналогично обосновывается цикличность перестановки 3 1 2.
Рисунок 1. Схема циклической перестановки 2 3 1.
Ниже будет представлена программа на языке программирования C++, реализующая генерацию и вывод всех циклических перестановок чисел от 1 до n.
#include <iostream>
using namespace std;
int X[100]; //Массив с N подряд идущими числами
int N; //Число элементов для перестановок
//Перемена мест двух соседних элементов массива
void Swap (int a, int b)
{
int t = X[a];
X[a] = X[b];
X[b] = t;
}
/*Проверка на наличие одного цикла в числе*/
bool iscorrect()
{
int a = X[0]; //Переменная для сравнения текущего элемента с первым
int size = 0; //Счётчик достигаемости
do //Пока не достигнут первый элемент сравнивать с ним последующие
{
a = X[a-1]; //Получение текущего элемента
size++; //Увеличить size
}
while(a != X[0]); //Сравнение текущего элемента с начальным
if (size < N) //Если size не достигает величины N, то цикла нет
{
return false;
}
else //size достиг величины N, значит имеет место цикл
{
return true;
}
}
/*Генерация всех перестановок*/
void Generate (int k)
{
if (k == N) //Одна перестановка завершена, вывод
{
if (iscorrect()) //Если есть циклическая престановка, то вывод
{
for (int i=0; i < N; i++)
{
std::cout << X[i] << " "; //Вывод каждого элемента через " "
}
std::cout << "\n"; //Вывод каждой перестановки через строку
}
}
else //Перестановка ещё не завершена, обработка элементов
{
//Перемещение элементов для построения перестановки
for (int j = k; j < N; j++)
{
Swap(k , j); //Поменять, если необходимо, элементы местами
Generate(k + 1); //Рекурсивный вызов (для следующего элемента)
Swap(k , j); // Финальное перемещение
}
}
}
/*Главная часть программы*/
int main()
{
//Пользовательские инструкции
std::cout << "Input N value please.\n";
std::cout << "N = ";
std::cin >> N; // Считывание введённого N
//Инициализация массива с N подряд идущими числами для перестановок
for (int i = 0; i < N; i++)
{
X[i] = i + 1;
}
//Вызов функции генерации всех циклических перестановок всех чисел от 1 до N
Generate(0);
}
Массив чисел для перестановки инициализируется подряд идущими значениями от 1 до n. Затем вызывается функция Generate(0); для генерации перестановок. В случае, если элементы нуждаются в перемене местами, вызывается функция Swap(k , j);. Далее происходит рекурсивный вызов функции Generate (k + 1) и переход к работе со следующим элементом. Завершается и выводится на экран одна перестановка, когда k становится равным N и в случае, если имеет место циклическая перестановка. Наличие циклической перестановки определяется булевой функцией bool iscorrect(). Эта функция сравнивает в цикле разные элементы с первым и увеличивает счётчик. Если счётчик достигает N, то цикл в последовательности есть. Далее обрабатываются остальные варианты перестановок.
Стоит отметить, что совокупная сложность алгоритма получения всех циклических перестановок чисел от 1 до n составляет n!.
