How to count the number of cycles in a permutation?

Question

C++ / C#

I have code to generate permutations of a given length, but I need to calculate the number of cycles for each permutation. Is there any algorithm for this?

#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

There is no way to somehow cunningly integrate the counting of cycles into the generation of permutations.
Therefore, the algorithm is simple - count the cycles one by one.
In fact, a permutation is a graph and you need to count the number of connected components in it. It is necessary to use DFS. But the graph is very simple, so DFS is expressed in a stupid cycle.
Get an array of flags as long as a permutation. Go through all the positions and, if the current one is not marked, start the second cycle from it, which will mark it and go to the permutation position ( row[i]) and mark it there and go again, and so on, until it comes across an already marked position. This way you will bypass one cycle and mark all positions in it. So add 1 to the counter when you run the inner loop.
The solution will have 2 nested loops, the outer one is most convenient to do for, the inner one can also be done for or while, but in for there will be a permutation transition instead of an increment. And these 2 nested loops will bypass all positions once in total, so the algorithm's running time is linear.