UVa 10570 - Meeting with Aliens

UVa Problem

This problem has to do with an important concept, permutation cycles.

Code:

#include <iostream>
#include <list>
#include <vector>

using namespace std;

typedef vector<int> perm;

list<perm> getPermCycles(perm p)
{
   const int N = p.size();
   list<perm> permCycles;
   vector<bool> used(N, false);

   for(int i = 0; i < N; ++i)
   {
      if(used[i] == false)
      {
         used[i] = true;
         perm newPerm;
         newPerm.push_back(i);

         int nextIndex = p[i];

         while(nextIndex != i)
         {
            newPerm.push_back(nextIndex);
            used[nextIndex] = true;
            nextIndex = p[nextIndex];
         }
         permCycles.push_back(newPerm);
      }
   }
   return permCycles;
}

int numSwaps(const list<perm>& perms)
{
   int result = 0;

   for(list<perm>::const_iterator i = perms.begin();
         i != perms.end(); ++i)
   {
      result += i->size();
   }

   result -= perms.size();

   return result;
}

perm mulPerm(perm perm1, perm perm2)
{
   perm result(perm1.size());
   perm inverted(perm1.size());

   for(int i = 0; i < inverted.size(); ++i)
      inverted[perm1[i]] = i;

   for(int i = 0; i < perm1.size(); ++i)
   {
      result[inverted[i]] = perm2[i];
   }

   return result;
}

int main(int argc, char *argv[])
{
   int N;

   while( (cin >> N) && N)
   {
      perm initPerm(N);
      perm rInitPerm(N);
      for(int i = 0; i < N; ++i)
      {
         cin >> initPerm[i];
         --initPerm[i];
         rInitPerm[N - i - 1] = initPerm[i];
      }

      int nSwaps = N - 1;

      perm identity(N);
      for(int i = 0; i < N; ++i)
         identity[i] = i;

      for(int i = 0; i < N; ++i)
      {
         perm res = mulPerm(identity, initPerm);
         nSwaps = min(nSwaps,
               numSwaps(getPermCycles(res)));

         res = mulPerm(identity, rInitPerm);
         nSwaps = min(nSwaps,
               numSwaps(getPermCycles(res)));

         for(int j = 0; j < N; ++j)
            identity[j] = (identity[j] + 1) % N;
      }
      cout << nSwaps << endl;
   }
   return 0;
}