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

//f-ja vraca nasumican ceo broj iz intervala (0,n-1)
int rand_int(int n) {
	return randi<int>(distr_param(0, n - 1));
}

//f-ja vraca nasumicnih k elemenata vektora x
uvec random_sample(uvec x, int k) {
	uvec r(k);
	int n = x.n_elem;
	if (k == 1)
		r(0) = x(rand_int(n));
	else {
		uvec pom = shuffle(x);
		r = pom(span(0,k-1));
	}
	return r;
}
//f-ja vraca razliku vektora u i v (u skupovnom smislu)
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++;
		}
	}
	return r(span(0, k-1));

}
//f-ja racuna vrednost funkcije cilja, tj. ukupnu duzinu ture x 
double f_cilja(uvec x, mat C) {
	double f = 0;
	int n = x.n_elem;
	for (int i = 0; i < n-1; i++)
	{
		f += C(x(i), x(i + 1));
	}
	f += C(x(n - 1), x(0));
	return f;
}
//operator zamene
//Vrsi se zamena elemenata na pozicijama ind(0) i ind (1)
uvec exchange(uvec x, uvec ind) {
	uvec x_e = x;
	x_e(ind(0)) = x(ind(1));
	x_e(ind(1)) = x(ind(0));
	return x_e;
}

//operator inverzije
//invertuju se elementi izmedju pozicija ind(0) i ind(1)
uvec inversion(uvec x, uvec ind) {
	uvec x_i = x;
	int n = x.n_elem;
	int l = min(ind);
	int d = max(ind);
	if (l == 0 && d == n - 1) {
		x_i = reverse(x);
		return x_i;
	}
	if (l == 0) {
		x_i = join_vert(reverse(x(span(l, d))), x(span(d + 1, n - 1)));
		return x_i;
	}
	if (d == n - 1) {
		x_i = join_vert(x(span(0, l - 1)), reverse(x(span(l, d))));
		return x_i;
	}
	x_i = join_vert(join_vert(x(span(0, l - 1)), reverse(x(span(l, d)))), x(span(d + 1, n - 1)));
	return x_i;

}
//operator umetanja
//element na poziciji ind(0) se umece na poziciju ind(1)
uvec insertion(uvec x, uvec ind) {
	int e = ind(0);
	int p = ind(1);
	uvec x_i=x;
	int n = x.n_elem;
	x_i.replace(x(p), x(e));

	if (e < p) {
		if (e <= 0) {
			x_i = join_vert(x(span(e + 1, p)), x_i(span(p, n - 1)));
		}
		else {
			x_i=join_vert(join_vert(x(span(0, e - 1)), x(span(e + 1, p))), x_i(span(p, n - 1)));
		}
	}
	else {
		if (e >= n - 1) {
			x_i = join_vert(x_i(span(0, p)), x(span(p, e - 1)));
		}
		else {
			x_i = join_vert(join_vert(x_i(span(0, p)), x(span(p, e - 1))), x_i(span(e + 1, n - 1)));
		
		}
	
	}

	return x_i;
}
//pomocna funkcija koja popunjava matricu I svim parovima indeksa za koje se moze vrsiti neka od
//transformacija umetanja/zamene/inverzije
//dimenzije je 2 x n*n-n, tj svaka kolona predstavlja jedan par indeksa 

void all_ind(umat& I, int n) {
	int k = 0;
	for (unsigned int i = 0; i < n; i++)
	{
		for (unsigned int j = 0; j < n; j++)
		{
			if (i != j)
			{
				I.col(k) = { i,j };
				k++;
			}
		}
	}
}
//f-ja radi lokalnu pretragu pocevsi od resenja x
//koristi se Best improvement strategija
//okoline se dobijaju primenom jednog od 3 ponudjena operatora:zamena, inverzija, umetanje
uvec local_search(uvec x, double f, mat C) {
	uvec x_best = x;
	double f_best = f;
	int n = x.n_elem;
	umat I = zeros<umat>(2,n*n-n);
	all_ind(I, n);
	umat P = zeros<umat>(n, n * n - n);
	int poboljsanje = 1;
	vec F = zeros<vec>(n * n - n, 1);
	while (poboljsanje) {
		//for petlja za generisanje citave okoline tekuceg resenja x_best
		//svaki sused je dobijen jednom primenom izabranog operatora na x_best
		//broj suseda jednak je broju mogucih parova, tj. broju kolona u matrici I
		for (int i = 0; i <n*n-n ; i++) {
			uvec pom = I.col(i);
			P.col(i) = inversion(x_best, pom);// ili exchange ili insertion
			F(i) = f_cilja(P.col(i), C);
		}
		//BI strategija za izbor novog suseda
		int indeks = F.index_min();
		if (F(indeks) < f_best) {
			f_best = F(indeks);
			x_best = P.col(indeks);

		}
		else
			poboljsanje = 0;
	
	}
	//cout << "f_best: " << f_best << endl;
	return x_best;
	
}
//f-ja radi lokalnu pretragu pocevsi od resenja x
//koristi se First improvement strategija
uvec local_search_FI(uvec x, double f, mat C) {
	uvec x_best = x;
	double f_best = f;
	int n = x.n_elem;
	umat I = zeros<umat>(2, n * n - n);
	all_ind(I, n);
	umat P = zeros<umat>(n, n * n - n);
	int poboljsanje = 1;
	vec F = zeros<vec>(n * n - n, 1);
	while (poboljsanje) {
		poboljsanje = 0; 
		//for petlja za generisanje okoline tekuceg resenja x_best
		//svaki sused je dobijen jednom primenom izabranog operatora na x_best
		//broj suseda jednak je broju mogucih parova, tj. broju kolona u matrici I
		for (int i = 0; i < n * n - n; i++) {
			uvec pom = I.col(i);
			P.col(i) = inversion(x_best, pom);//ili exchange ili insertion
			F(i) = f_cilja(P.col(i), C);
			if (F(i) < f_best) {
				f_best = F(i);
				x_best = P.col(i);
				poboljsanje = 1; 
				break; //izlaz iz for petlje: ne pretrazujemo celu okolinu, vec pretragu odmah nastavljamo od novog x_best
			}		
		
		}
		

	}
	//cout << "f_best: " << f_best << endl;
	return x_best;

}




int main(int argc, char** argv) {
	//uvec u = { 1,2,6,9,15,18,22,26 };
	//uvec v = { 1,2,6,9,11,15,17 };
	//cout << "u razlika v: " << u_diff_v(u,v) << endl;
	//cout << "Nasumicni elementi iz v: " << random_sample(v, 3) << endl;
	//cout << "Reverse: " << inversion(u, { 2, 6 }) << endl;
	//cout << "Insertion: " << insertion(u, {5,3}) << endl;
	//ucitavamo podatke
	ifstream data("fri26.txt");
	int n = 0;
	data >> n;
	mat C = zeros<mat>(n, n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++) {
			data >> C(i, j);
		}
	}
	//uvec x=zeros<uvec>(10);

	//x-inicijalno random resenje
	uvec v = linspace<uvec>(0, n - 1, n);   //0,1,2,3,....n-1
	uvec x = shuffle(v);
	double f = f_cilja(x, C);
	
	//****LS********
	uvec x_best = local_search(x, f, C);
	cout << "LS resenje: " << x_best << endl;
	
	//*****MS******
	uvec x_ms = zeros<uvec>(n, 1); //najbolje resenje nakon svih pokretanja
	double f_ms = datum::inf;
	int iter = 200; //broj pokretanja
	for (int i = 0; i < iter; i++)
	{
		uvec x_i = shuffle(v);
		double f_i = f_cilja(x_i, C);
		uvec x_ls = local_search(x_i, f_i, C);
		double f_ls = f_cilja(x_ls, C);
		if (f_ls < f_ms) {
			f_ms = f_ls;
			x_ms = x_ls;
		}
	}
	cout << "Multistrat LS:" << x_ms << endl;
	cout << "f_best za MSLS: " << f_ms << endl;

	


}