JPermutation.cc

Go to the documentation of this file.

#include <string>
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <algorithm>

#include "JTools/JPermutation.hh"
#include "JMath/JMathToolkit.hh"

#include "Jeep/JParser.hh"
#include "Jeep/JMessage.hh"


/**
 * \file
 *
 * Example program to test permutations (JTOOLS::next_permutation).
 * \author mdejong
 */
int main(int argc, char **argv)
{
  using namespace std;

  vector<int>    buffer;
  unsigned int   N;
  int            debug;

  try { 

    JParser<> zap("Example program to test permutations.");
    
    zap['i'] = make_field(buffer);
    zap['N'] = make_field(N);
    zap['d'] = make_field(debug)               = 1;
    
    zap(argc, argv);
  }
  catch(const exception &error) {
    FATAL(error.what() << endl);
  }


  using namespace JPP;


  if (N > buffer.size()) {
    FATAL("Number of elements " << N << " > " << buffer.size() << endl);
  }

  sort(buffer.begin(), buffer.end(), less<int>());
  
  vector<int>::iterator p = buffer.begin();
  
  advance(p, N);

  vector< set<int> > data;
  
  int n = 0;
  
  do {
    
    ++n;
    
    DEBUG('[' << setw(3) << n << ']');

    for (vector<int>::const_iterator i = buffer.begin(); i != p; ++i) {
      DEBUG(' ' << setw(3) << *i);
    }

    data.push_back(set<int>());
    
    for (vector<int>::const_iterator i = buffer.begin(); i != p; ++i) {
      data.rbegin()->insert(*i);
    }
    
    DEBUG("  |");

    for (vector<int>::const_iterator i = p; i != buffer.end(); ++i) {
      DEBUG(' ' << setw(3) << *i);
    }

    DEBUG(endl);
    
  } while (next_permutation(buffer.begin(), p, buffer.end(), less<int>()));


  for (vector< set<int> >::const_iterator p = data.begin(); p != data.end(); ++p) {
    for (vector< set<int> >::const_iterator q = p; ++q != data.end(); ) {
      ASSERT(*p != *q);
    }
  }

  
  NOTICE("number of permutations " << n << ' ' << factorial(buffer.size(), N) << endl);

  ASSERT(n == factorial(buffer.size(), N));
}