Given a positive integer n, gives number of elements of each order present in a symmetric group of order n. This is used to verify the solution of problem: CSE-2013-2(b).

elementOrderSn.cpp

/* 

Program description: Given a positive integer n, gives number of elements of each order present in a symmetric group of order n.
This is used to verify the solution of problem: CSE-2013-2(b).

*/

#include <iostream>
#include <vector> 
#include <map>

typedef long long int lli;

using namespace std;

int gcd (int a, int b) {
  return b == 0 ? a : gcd (b, a % b);
}

int lcm (int a, int b) {
  return (a / gcd(a, b)) * b;
}

int getOrder (vector<int> &perm) {
  int k = 0;
  int order = 1;
  vector<bool> isSeen(perm.size(), false);
  while (k != perm.size()) {
    if (isSeen[k]) {
      k++;
      continue;
    }
    int st = perm[k];
    int at = st;
    int len = 0;
    do {
      at = perm [at - 1];
      len++;
      isSeen[at - 1] = true;
    } while (at != st);
    order = lcm (order, len);
    k++;
  }
  return order;
}


int main () {
  int n;
  cout << "Enter n: \n";
  cin >> n;
  vector<int> perm;
  map<int, lli> permOrder;
  for (int i = 0; i < n; i++) {
    perm.push_back(i + 1);
  }
  do {
    permOrder[getOrder(perm)]++;
    // for (int i = 0; i < n; i++) {
    //   cout << perm[i] << " ";
    // }
    // cout << "\n";
  } while (next_permutation(perm.begin(), perm.end()));
  for (auto it = permOrder.begin(); it != permOrder.end(); it++) {
    cout << it->first << " " << it->second << "\n";
  }
  return 0;
}