Project Euler Homework

032_permutation.h

Go to the documentation of this file.
00001 
00004 #ifndef _INCL_032_perm032
00005 #define _INCL_032_perm032
00006 #include <iostream>
00007 using namespace std;
00008 
00009 typedef int digit;
00010 typedef unsigned idx;
00011 
00012 class perm032
00014 {
00015   idx swap_idx;
00016   perm032 *sub_permObj;
00017   void make_sub_perm ();
00018   void swap_digits (idx, idx);
00019   unsigned N;                   
00020   digit *perm;                  
00021 public:
00022     perm032 (unsigned); 
00023     perm032 (digit *, unsigned);        
00024    ~perm032 ();         
00025   bool next ();                 
00026   void print_perm ();           
00027   int operator[] (idx);         
00028   unsigned length ();           
00029 };
00030 
00031 perm032::perm032 (unsigned N)
00033 {
00034   this->N = N;
00035   perm = new int[N];
00036   for (int i = 0; i < N; i++)
00037     perm[i] = i + 1;
00038 
00039   make_sub_perm ();
00040   swap_idx = 0;
00041 }
00042 
00043 perm032::perm032 (digit * perm2, unsigned length)
00047 {
00048   this->N = length;
00049   perm = new int[length];
00050 
00051   for (int i = 0; i < length; i++)
00052     perm[i] = perm2[i];
00053 
00054   make_sub_perm ();
00055   swap_idx = 0;
00056 }
00057 
00058 void
00059 perm032::make_sub_perm ()
00060 {
00061   if (N > 2)
00062     sub_permObj = new perm032 (perm + 1, N - 1);
00063   else
00064     sub_permObj = 0;
00065 }
00066 
00067 perm032::~perm032 ()
00068 {
00069   delete[]perm;
00070   delete sub_permObj;
00071 }
00072 
00073 bool perm032::next ()
00074 {
00075   //First exhausts perm032 of digits excluding the first
00076   if (N > 2)
00077     if (sub_permObj->next ())
00078       return 1;
00079 
00080   // if no more perm032 could be found in subset, resume to initial perm032
00081   if (swap_idx)
00082     swap_digits (0, swap_idx);
00083 
00084   swap_idx++;
00085   if (swap_idx == N)
00086     return 0;                   //If no more possible values
00087 
00088   swap_digits (0, swap_idx);    //find new possible value for the first digit
00089 
00090   delete
00091     sub_permObj;
00092   make_sub_perm ();
00093 
00094   return 1;
00095 }
00096 
00097 void
00098 perm032::swap_digits (unsigned x, unsigned y)
00102 {
00103   digit temp = perm[x];
00104   perm[x] = perm[y];
00105   perm[y] = temp;
00106 }
00107 
00108 int
00109 perm032::operator[] (idx k)
00110 {
00111   if (k == 0)
00112     return perm[0];
00113   else if (N == 2 && k == 1)
00114     return perm[1];
00115 
00116   return (*sub_permObj)[k - 1];
00117 }
00118 
00119 void
00120 perm032::print_perm ()
00121 {
00122   cout << char (perm[0] + '0'); //First digit
00123   if (N == 2)
00124     cout << char (perm[1] + '0');
00125   else
00126     sub_permObj->print_perm ();
00127 }
00128 
00129 unsigned
00130 perm032::length ()
00131 {
00132   return N;
00133 }
00134 
00135 #endif
 All Classes Files Functions Variables