projet_optim_m2/src/permutation.cpp

#include "permutation.h"
#include <algorithm> // swap
#include <cstdlib> // rand
#include <cassert>

// TODO faut-il pi[0] = 0 et pourquoi ???
permutation::permutation(int size) : size(size) {
  assert(size > 0);
  sigma = new int[size];
  for(int i = 0; i < size; i++)
    sigma[i] = i;
}

void permutation::transpose(int i, int j) {
  assert(0 <= i && i < size);
  assert(0 <= j && j < size);
  std::swap(sigma[i], sigma[j]);
}

void permutation::random() {
  // Knuth shuffle
  // TODO algo plus efficace ?
  // there is a bias due to the use of rand()%_
  for(int i = 0; i < size; i++)
    transpose(i, rand()%(i+1));
}

int permutation::operator[](int i) {
  assert(0 <= i && i < size);
  return sigma[i];
}