043_permutation.h

Go to the documentation of this file.

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

typedef int digit;
typedef unsigned idx;

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

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

  make_sub_perm ();
  swap_idx = 0;
}

perm043::perm043 (digit * perm2, unsigned length)
{
  size = length;
  perm = new int[length];

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

  make_sub_perm ();
  swap_idx = 0;
}

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

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

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

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

  swap_idx++;
  if (swap_idx == size)
    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
perm043::swap_digits (unsigned x, unsigned y)
{
  digit temp = perm[x];
  perm[x] = perm[y];
  perm[y] = temp;
}

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

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

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

unsigned
perm043::length ()
{
  return size;
}

#endif