#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <armadillo>
#pragma warning(disable:4996)
using namespace std;
using namespace arma;

int rand_int(int n) {
	return randi<int>(distr_param(0, n - 1));
}
uvec random_sample(uvec x, int k) {
	int n = x.n_elem;
	uvec sample(k);
	if (k == 1)
		sample(0) = x(rand_int(n));
	else {
		uvec pom = shuffle(x);
		sample = pom(span(0, k - 1));
	}
	return sample;
}
uvec u_diff_v(uvec u, uvec v) {
	int n = u.n_elem;
	uvec r(n);
	int k = 0;
	for (int i = 0; i < n; i++)
	{
		if (!any(u(i) == v)) {
			r(k) = u(i);
			k++;
		}
	}
	if (k == 0)
		return uvec();
	else
		return r(span(0, k - 1));
}

void inicijalna_populacija(umat& P,int size_p, int n, int p) {
	umat X = zeros<umat>(size_p, p);//svaka vrsta sadrzi jednu jedinku
	uvec jedinka;
	uvec all = linspace<uvec>(0, n - 1, n);
	for (int i = 0; i < size_p; i++)
	{
		jedinka = random_sample(all, p);
		for (int j = 0; j <p ; j++)
		{
			X(i, j) = jedinka(j);
		}
	}

	P = X;
}
//f-ja cilja za jedinku x
void f_cilja(urowvec x, mat C, int n, int p, double& f) {
	f=0;
	mat Cx = C.cols(x);
	uvec all = linspace<uvec>(0, n - 1, n);

	for (int i = 0; i < n; i++)
	{
		int korisnik = all(i);
		f+= min(Cx.row(korisnik));
		
	}	
}

//f-ja prilagodjenosti za sve jedinke iz populacije P
void f_prilagodjenosti(vec&F,umat P, int n, int p, mat C) {
	int size_p = P.n_rows;
	vec pom = zeros<vec>(size_p);

	for (int i = 0; i < size_p; i++)
	{
	f_cilja(P.row(i), C, n, p, pom(i));
	}
	F = pom;
}

void selekcija(umat P, umat& new_P, vec F, vec& new_F, int p) {
	int size_p = P.n_rows;
	umat SP(size_p, p);
	vec SF(size_p);
	int ind;
	uvec index_F = sort_index(F);//sortiramo jedinke rastuce po vrednosti f-je cilja
	for (int i = 0; i < size_p; i++) {
		ind = size_p - floor((-1 + sqrt(1 + 4 * randu<double>() * (size_p * size_p + size_p))) * 0.5) - 1;
		SP.row(i) = P.row(index_F(ind));
		SF(i) = F(index_F(ind));
	}
	new_P = SP;
	new_F = SF;
}
//20% najboljih selektovanih jedinki ide direktno u sledecu generaciju, ostatak nove generacije
//cine potomci dobijeni ukrstanjem

void ukrstanje(umat P, umat SP, umat& new_P, vec F, vec SF) {
	int p = P.n_cols;
	int size_p = P.n_rows;
	int stari = floor(0.20 * size_p);
	uvec sort_ind_P = sort_index(F);  //sortirane sve jedinke
	uvec sort_ind_SP = sort_index(SF);//sortirane selektovane jedinke
	umat potomci(size_p, p);

	for (int i = 0; i < stari; i++) {
		potomci.row(i) = P.row(sort_ind_SP(i));
	}

	for (int i = 0; i < size_p - stari; i++) {
		int k = randi(distr_param(1, p - 2));
		//jednopoziciono ukrstanje
		urowvec dP = P.row(sort_ind_P(i));
		urowvec dSP = SP.row(sort_ind_SP(i));
		potomci.row(stari + i) = join_horiz(dP(span(0, k)), dSP(span(k + 1, p - 1)));
	}
	new_P = potomci;
}

//svaka jedinka sa verovatnocom 0.1 menja jednu medijanu (gen mutira sa verovatnocom 0.1/p)
void mutacija(umat& new_G, int n) {
	int size_p = new_G.n_rows;
	int p = new_G.n_cols;
	uvec all = linspace<uvec>(0, n - 1, n);
	uvec pom = linspace<uvec>(0, p - 1, p);

	for (int i = 0; i < size_p; i++) {
		if (randu<double>() > 0.9) {//jedinka mutira
			uvec ind_m = random_sample(pom, 1);//nasumicno birmo gen koji mutira
			uvec jedinka(p);
			for (int j = 0; j < p; j++) {
				jedinka(j) = new_G(i, j);//kopiramo jedinku
			}
			uvec mutirani_gen = random_sample(u_diff_v(all, jedinka), 1);//nasumicno biramo centar koji nije deo resenja
			new_G(i, ind_m(0)) = mutirani_gen(0);
		}
	}
}




int main() {

	ifstream data("berlin52.txt");
	int n, p;
	data >> n;
	data >> p;
	mat C = zeros<mat>(n, n);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++) {
			data >> C(i, j);
		}
	}

	

	int size_p = 100; //broj jedinki
	int max_gen = 100; //kriterijum zaustavljanja: maksimalan broj generacija
	umat P;
	umat new_P;
	umat new_G;
	vec F;
	vec new_F;
	vec new_GF;
	urowvec X_best;
	double F_best;
	inicijalna_populacija(P,size_p,n, p);

	f_prilagodjenosti(F, P, n, p, C);

	int ind = index_min(F);
	X_best = P.row(ind);
	F_best = F(ind);

	for (int i = 0; i < max_gen; i++) {
		selekcija(P, new_P, F, new_F, p);

		ukrstanje(P, new_P, new_G, F, new_F);


		mutacija(new_G, n);
		f_prilagodjenosti( new_GF, new_G, n, p, C);
		i++;
		cout << i << endl << F_best << endl;
		P = new_G;
		F = new_GF;
		if (F_best >= min(F)) {
			ind = index_min(F);
			X_best = P.row(ind);
			F_best = F(ind);
		}
	}
	return 0;













}