123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596 |
- #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;
- }
- int permutation::get_size() {
- return size;
- }
- // 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;
- }
|