Как посчитать количество циклов у перестановки?

Question

[fjaerj12]

У меня есть код для генераций перестановок указанной длины, но мне нужно вычислить количество циклов у каждой перестановки. Есть ли какой-то алгоритм для этого?

#include <iostream>
#include <vector>

bool newSet(std::vector<int>&row, int length) 
{
	int j = length - 2;

	while ((j > -1) && (row[j] > row[j + 1])) j--;

	if (j == -1) return false;

	int right = length - 1;

	while (row[j] > row[right]) right--;
	std::swap(row[j], row[right]);

	int left = j + 1;
	right = length - 1;

	while (left < right) 
	{
		std::swap(row[left], row[right]);
		left++;
		right--;
	}
	return true;
}

int main()
{
	int length = 0;
	std::cout << "Input a length of the set ";
	std::cin >> length;

	if (length > 0) 
	{
		std::vector<int> row;

		for (int i = 0; i < length; i++) row.push_back(i + 1);

		std::cout << "1) ";
		for (int i = 0; i < length; i++) std::cout << row[i] << " ";
		std::cout << '\n';

		int number = 2;
		while (newSet(row, length))
		{
			std::cout << number << ") ";
			number++;
			for (int i = 0; i < length; i++) std::cout << row[i] << " ";
			std::cout << '\n';
		}
	}
	else
	{
		std::cout << "Error. The length of the set must be more than 0";
	}	
}

Answer 1

[Wataru]

Как-то хитро встроить подсчет циклов в генерацию перестановок никак не получится.

Поэтому, алгоритм простой - посчитать циклы по одному.
Фактически, перестановка - это граф и вам надо подсчитать в нем количество компонент связности. Надо использовать DFS. Но граф очень простой, поэтому DFS выраждается в тупо цикл.

Заведите массив флагов длинной с перестановку. Пройдитесь по всем позициям и, если текущая не помечена, запускайте от нее второй цикл, который пометит ее и перейдет в позицию по перестановке (row[i]) и пометит там и опять перейдет и так далее, пока не наткнется на уже помеченную позицию. Так вы побойдете один цикл и пометите все позиции в нем. Поэтому прибавьте 1 к счетчику, когда будете запускать внутренний цикл.

В решении будет 2 вложенных цикла, внешний - удобнее всего делать for, внутренний можно тоже делать for или while, но в for будет вместо инкримента переход по перестановке. И эти 2 вложенных цикла суммарно обойдут все позиции по одному разу, поэтому время работы алгоритма - линейное.