032_permutation.h

Go to the documentation of this file.

#ifndef _INCL_032_perm032
#define _INCL_032_perm032
#include <iostream>
using namespace std;

typedef int digit;
typedef unsigned idx;

class perm032
{
  idx swap_idx;
  perm032 *sub_permObj;
  void make_sub_perm ();
  void swap_digits (idx, idx);
  unsigned N;                   
  digit *perm;                  
public:
    perm032 (unsigned); 
    perm032 (digit *, unsigned);        
   ~perm032 ();         
  bool next ();                 
  void print_perm ();           
  int operator[] (idx);         
  unsigned length ();           
};

perm032::perm032 (unsigned N)
{
  this->N = N;
  perm = new int[N];
  for (int i = 0; i < N; i++)
    perm[i] = i + 1;

  make_sub_perm ();
  swap_idx = 0;
}

perm032::perm032 (digit * perm2, unsigned length)
{
  this->N = length;
  perm = new int[length];

  for (int i = 0; i < length; i++)
    perm[i] = perm2[i];

  make_sub_perm ();
  swap_idx = 0;
}

void
perm032::make_sub_perm ()
{
  if (N > 2)
    sub_permObj = new perm032 (perm + 1, N - 1);
  else
    sub_permObj = 0;
}

perm032::~perm032 ()
{
  delete[]perm;
  delete sub_permObj;
}

bool perm032::next ()
{
  //First exhausts perm032 of digits excluding the first
  if (N > 2)
    if (sub_permObj->next ())
      return 1;

  // if no more perm032 could be found in subset, resume to initial perm032
  if (swap_idx)
    swap_digits (0, swap_idx);

  swap_idx++;
  if (swap_idx == N)
    return 0;                   //If no more possible values

  swap_digits (0, swap_idx);    //find new possible value for the first digit

  delete
    sub_permObj;
  make_sub_perm ();

  return 1;
}

void
perm032::swap_digits (unsigned x, unsigned y)
{
  digit temp = perm[x];
  perm[x] = perm[y];
  perm[y] = temp;
}

int
perm032::operator[] (idx k)
{
  if (k == 0)
    return perm[0];
  else if (N == 2 && k == 1)
    return perm[1];

  return (*sub_permObj)[k - 1];
}

void
perm032::print_perm ()
{
  cout << char (perm[0] + '0'); //First digit
  if (N == 2)
    cout << char (perm[1] + '0');
  else
    sub_permObj->print_perm ();
}

unsigned
perm032::length ()
{
  return N;
}

#endif