#include <iostream>

int** Create(int N, int  maxRange)
{
	int **Matrix = new int *[N];
	if (Matrix == NULL) //if N == 0
		return Matrix;
	srand(0);
	for (int i = 0; i < N; i++)
	{
		Matrix[i] = new int[N];
		for (int j = 0; j < N; j++)
		{

			if (i == j)
				Matrix[i][j] = 0;
			else
				Matrix[i][j] = rand() % maxRange + 1;//from 1 to RANGE_MAX
			std::cout << Matrix[i][j] << ' ';
		}
		std::cout << '\n';
	}
	std::cout << '\n';
	return Matrix;
}

void swap(int *i, int *j)
{
	int s = *i;
	*i = *j;
	*j = s;
}

bool NextSet(int *a, int n)
{
	int j = n - 2;
	for (; j != -1 && a[j] >= a[j + 1]; j--);
	if (j == -1)
		return false; // больше перестановок нет
	int k = n - 1;
	for (; a[j] >= a[k]; k--);
	swap(&a[j], &a[k]);
	int l = j + 1, r = n - 1;
	while (l < r)
	{
		swap(&a[l++], &a[r--]);
	}
	return true;
}
template <typename T>
void CopyArray(T *arr, T *source, int sourceLen, int start = 0)
{
	for (int i = 0; i < sourceLen; i++)
	{
		arr[i + start] = source[i];
	}
}

int FindPrice(int **matrix, int *order, int n)
{
	int price = 0;
	for (int i = 1; i < n; i++)
	{
		price += matrix[order[i - 1]][order[i]];
	}
	price += matrix[order[n - 1]][order[0]];
	return price;
}

int *FindBestWay(int **matrix,int citiesCount)
{
	int *curentWay = new int[citiesCount];
	int *bestWay = new int[citiesCount];
	int bestWayLength = INT16_MAX;
	int curentWayLength;
	for (int i = 0; i < citiesCount; i++)
	{
		curentWay[i] = i;
	}

	while (NextSet(curentWay, citiesCount))
	{
		curentWayLength = FindPrice(matrix, curentWay, citiesCount);
		if (curentWayLength < bestWayLength)
		{
			bestWayLength = curentWayLength;
			CopyArray(bestWay, curentWay, citiesCount);
		}
	}
	return bestWay;
}

int main()
{
	int **matrix = Create(4, 10);
	int *way = FindBestWay(matrix, 4);
	for (int i = 0; i < 4; i++)
	{
		std::cout << way[i] + 1 << ' ';
	}
	std::cout << '\n'<< "Way Lentgth: " << FindPrice(matrix, way, 4);
	return 0;
}