projet_optim_m2/src/permutation.cpp

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

using namespace std;

permutation::permutation(int size) : size(size), sigma(size) {
  assert(size > 0);
  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]);
}

// TODO rapport : dire qu'on garde l'invariant pi[0] = 0
void permutation::random() {
  // Knuth shuffle
  // there is a bias due to the use of rand()%_
  for(int i = 1; i < size; i++)
    transpose(i, 1+rand()%i);
}

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

bool permutation::check() {
  if(size != (int)sigma.size() || sigma[0] != 0)
    return false;
  vector<bool> seen(size);
  for(int i = 0; i < size; i++)
    seen[sigma[i]] = true;
  for(int i = 0; i < size; i++)
    if(!seen[i])
      return false;
  return true;
}

// Algorithm:
// for each i (randomly : we use a permutation :P (it always starts with 0 but
// it's OK since a[0]=b[0]=0 and also we want ret[0]=0))
// we choose either a[i] or b[i]
// if one value was already choosen, we choose the other
// if both were, we choose a value we have seen but not choose (in the set disp)
permutation permutation_crossover(permutation &a, permutation &b) {
  assert(a.size == b.size);
  permutation ret(a.size);
  permutation ord(a.size); // order in which we consider elements of permutations a and b
  vector<bool> seen(a.size);
  set<int> disp;
  ord.random();
  for(int i = 0; i < a.size; i++) {
    int j = ord[i];
    bool seen_a = seen[a[j]], seen_b = seen[b[j]];
    if(seen_a && seen_b) {
      // take a random value in disp
      assert(disp.size()>0);
      auto it = disp.begin();
      advance(it, rand()%disp.size());
      ret.sigma[i] = *it;
    }
    else if(seen_a) {
      // take value in b
      ret.sigma[i] = b[j];
    }
    else if(seen_b) {
      // take value in a
      ret.sigma[i] = a[j];
    }
    else if(rand()%2) {
      // take value in b
      ret.sigma[i] = b[j];
      disp.insert(a[j]);
    }
    else {
      // take value in a
      ret.sigma[i] = a[j];
      disp.insert(b[j]);
    }
    seen[ret[i]] = true;
    disp.erase(ret[i]);
  }
  assert(ret.check());
  return ret;
}