024.cpp

Go to the documentation of this file.

#include <iostream>
using namespace std;

const int digits = 10;
class permutation
{
  static unsigned count;
  static bool flag;
  unsigned short x[digits];
  int begin;
  int end;
public:
    permutation ();
    permutation (unsigned short *y, int a, int b);
  void swap (int a, int b);
  void printP ();
  void move_to (unsigned k);
};

unsigned
  permutation::count = 0;
bool permutation::flag = 0;

permutation::permutation ()
{
  unsigned short *p = x;
  for (int i = 0; i < digits; i++, p++)
    *p = i;

  begin = 0;
  end = digits - 1;
}

permutation::permutation (unsigned short *y, int a, int b)
{
  unsigned short *p = x;
  for (int i = 0; i < digits; i++, p++, y++)
    *p = *y;

  begin = a;
  end = b;
}

void
permutation::printP ()
{
  for (int i = 0; i < digits; i++)
    cout << x[i];
  cout << endl;
}

void
permutation::swap (int a, int b)
{
  unsigned short tmp = x[a];
  x[a] = x[b];
  x[b] = tmp;
}

void
permutation::move_to (unsigned k)
{
  if (end - begin == 1)         //only two digits
    {
      count += 2;               //only two possible permutations
      if (count == k)           //reached desired permutation
        {
          this->swap (begin, end);
          this->printP ();      //print the permutation
          flag = 1;             //stop the recursion
          return;
        }
      else if (count == k + 1)  //or go beyond the desired permutation
        {
          this->printP ();
          flag = 1;
          return;
        }
      else if (count > k)       //error, stop the process
        {
          cout << "An error had encountered when processing digits " << begin
            << " to " << end << ":\n";
          this->printP ();
          cout << "Count = " << count << endl;
          flag = 1;
          return;
        }
    }

  else                          //if more than two digits
    for (int idx = begin; idx <= end; idx++)
      {
        this->swap (begin, idx);        //try new permutation

        permutation *newlist = new permutation (x, begin + 1, end);     //copy to new string
        newlist->move_to (k);   //recursion relies on here
        delete newlist;

        if (flag)               //break the loop if the desired value has been reached
          break;
      }
}

int
main ()
{
  permutation list;
  list.move_to (1000000);       //find the one millionth permutation

  return 0;
}