bia.cpp

#include <iostream>
#include <vector>
#include <stdio.h>
#include <random>
#include <chrono>

class Point {

public:
	double x, y;
	int id;
	static int idGenerator;
	Point() {}
	Point(double x, double y) :x(x), y(y), id(idGenerator++) {  }
	double distance_between(Point &other) {
		return std::sqrt((other.x - this->x) * (other.x - this->x) + (other.y - this->y) * (other.y - this->y));
	}
};
int Point::idGenerator = 0;

template <typename T>
void perm(std::vector<T> &input, int index, void(*action)(std::vector<T>&)) {
	if (index == input.size()) {
		(*action)(input);
	}
	else {
		perm(input, index + 1, action);

		for (int i = index + 1; i < input.size(); i++)
		{
			std::swap(input[i], input[index]);
			perm(input, index + 1, action);
			std::swap(input[index], input[i]);
		}
	}
}
Point * selectedFirst;
double maxDistance = 0, minDistance = 1000000000.0;
void permutationAction(std::vector<Point> &permutation) {
	double distance = 0;
	distance += selectedFirst->distance_between(permutation[0]);
	for (unsigned int i = 0; i < permutation.size() - 1; i++) {
		distance += permutation[i].distance_between(permutation[i + 1]);
	}
	distance += permutation[permutation.size() - 1].distance_between(*selectedFirst);
	if (distance > maxDistance) {
		maxDistance = distance;
	}
	if (distance < minDistance) {
		minDistance = distance;
	}
}

const int min = 3;
const int max = 13;

int main() {
	std::default_random_engine generator;
	std::uniform_real_distribution<double> distribution(1.0, 10.0);


	for (unsigned i = min; i <= max; i++) {
		std::chrono::time_point<std::chrono::system_clock> start, end;

		Point::idGenerator = 0;
		std::vector<Point> input, prefix;
		input.reserve(i - 1);
		prefix.reserve(i - 1);
		selectedFirst = &Point(distribution(generator), distribution(generator));
		start = std::chrono::system_clock::now();
		maxDistance = 0;
		minDistance = 1000000000.0;
		for (unsigned j = 0; j < i - 1; j++) {
			input.push_back(Point(distribution(generator), distribution(generator)));
		}

		perm(input, 0, permutationAction);
		printf("Max distance: %f\n", maxDistance);
		printf("Min distance: %f\n", minDistance);
		end = std::chrono::system_clock::now();
		printf("Count %d ended in %d\n", i, std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count());
		printf("--------------------\n");
	}
	getchar();
	return 0;
}