#include <iostream>
#include <random>
#include <cassert>
#include <vector>
#include <list>
#include <algorithm>
#include <array>
#include <set>
#include <memory.h>
using namespace std;
//行列、测试列（本例子取8）
template<int R, int C, int T>
class tag_item {
public:
	tag_item(){
		for (int i=0;i<T;++i)
			coords[i] = 0;
	}
	tag_item(const tag_item & t){
		memcpy(coords,t.coords,sizeof(coords));
		good = t.good;
	}
	int coords[T];
	int	good = 0;
public:
	inline bool operator == (const tag_item & t) const
	{
		for (int i=0;i<T;++i)
			if (t.coords[i]!=coords[i])
				return false;
		return true;
	}
	inline tag_item & operator = (const tag_item & t)
	{
		for (int i=0;i<T;++i)
			coords[i] = t.coords[i];
		good = t.good;
		return *this;
	}
	inline int cal_good(const char (* data)[C]) const
	{
		int res = 0;
		for (int i = 0; i < R; ++i)
		{
			bool failed = false;
			for (int j = 0; j < T && !failed; ++j)
			{
				if (!data[i][coords[j]])
					failed = true;
			}
			if (!failed)
				++res;
		}
		return res;
	}
	inline void output() const
	{
		using std::cout;
		cout << "Weight=" << good <<" Cols: ";
		for (int i = 0; i < T; ++i)
			cout << " " << coords[i];
		cout << "\n";
	}
	inline void sort()
	{
		std::sort(coords,coords+T,std::less<int>());
	}
};
template<int R, int C, int T>
inline bool operator < (const tag_item <R,C,T>& t1, const tag_item <R,C,T>& t2) {
	for (int i = 0; i < T; ++i)
	{
		if (t1.coords[i] < t2.coords[i])
			return true;
		else if (t1.coords[i] > t2.coords[i])
			return false;
	}
	return false;
}

int main(int /*argc*/, char* /*argv*/[])
{
	using namespace std;
	default_random_engine e;
	const int R = 5000, C = 5000, T=8;
	typedef tag_item<R,C,T> citem;
	char(*data)[C] = new char[R][C];
	assert(data);
	for (int i = 0; i < R; ++i)
		for (int j = 0; j < C; ++j)
			data[i][j] = e() % 2;
	int best[8] = {12,445,17,2314,3033,1273,2289,4987};
	//Best rows,重量一致，但是排齐
	for (int i = 0; i <R ; ++i)
		for (int j = 0; j < 8; ++j)
			data[i][best[j]] = 0;
	for (int i = 0; i <R/2 ; ++i)
	{
		int r = e() % R;
		for (int j = 0; j < 8; ++j)
		{
			data[r][best[j]] = 1;
		}
	}

	//种群1024
	const int S = 1024;
	vector<citem> group;
	std::set<citem> group_set;
	//产生初始集合
	for (int i = 0; i < S; ++i)
	{
		citem tmp;
		for (int j = 0; j < T; ++j)
		{
			bool failed = false;
			do {
				tmp.coords[j] = e() % C;
				failed = false;
				if (j)
				{
					for (int k = 0; k < j && !failed; ++k)
						if (tmp.coords[k] == tmp.coords[j])
							failed = true;
				}
			} while (failed);
		}
		tmp.sort();
		tmp.good = tmp.cal_good(data);

		if (group_set.find(tmp)== group_set.end())
		{
			group_set.insert(tmp);
			group.push_back(tmp);
		}
		else
			--i;
	}


	//开始遗传优化K次
	const int K = 1<<20;
	for (int g = 0; g < K; ++g)
	{
		vector<citem> new_group;
		//交叉
#pragma omp parallel for
		for (int i = 0; i < S; ++i)
		{
			set<int> cols;
			vector<int> cols_v;
			for (int j = 0; j < T; ++j)
			{
				cols.insert(group[i].coords[j]);
				cols_v.push_back(group[i].coords[j]);
			}
			const int s = e() % S;
			citem nw;
			if (s != i)
			{
				for (int j = 0; j < T; ++j)
				{
					if (cols.find(group[s].coords[j]) == cols.end())
					{
						cols_v.push_back(group[s].coords[j]);
						cols.insert(group[s].coords[j]);
					}

				}
				const size_t sz_set = cols_v.size();
				for (int b = 0; b < T; ++b)
				{
					const int take = e() % (sz_set - b);
					auto iter = cols_v.begin() + take;
					nw.coords[b] = *iter;
					cols_v.erase(iter);
				}
				nw.good = nw.cal_good(data);
				nw.sort();
#pragma omp critical
				new_group.push_back(nw);
			}
		}
		//复制
		std::copy(new_group.begin(), new_group.end(), back_inserter(group));
		new_group.clear();
		const size_t S2 = group.size();
		//变异
#pragma omp parallel for
		for (size_t i = 0; i < S2; ++i)
		{
			const int b = e() % T;
			citem nw = group[i];
			bool failed = false;
			do {
				nw.coords[b] = e() % C;
				failed = false;
				for (int k = 0; k < T && !failed; ++k)
					if (nw.coords[b] == nw.coords[k] && b!=k)
						failed = true;
			} while (failed);
			nw.good = nw.cal_good(data);
			nw.sort();
#pragma omp critical
			new_group.push_back(nw);
		}
		std::copy(new_group.begin(), new_group.end(), back_inserter(group));
		new_group.clear();

		//增补
		for (int i = 0; i < S/4; ++i)
		{
			citem tmp;
			for (int j = 0; j < T; ++j)
			{
				bool failed = false;
				do {
					tmp.coords[j] = e() % C;
					failed = false;
					if (j)
					{
						for (int k = 0; k < j && !failed; ++k)
							if (tmp.coords[k] == tmp.coords[j])
								failed = true;
					}
				} while (failed);
			}
			tmp.sort();
			tmp.good = tmp.cal_good(data);

			if (group_set.find(tmp)== group_set.end())
			{
				group_set.insert(tmp);
				group.push_back(tmp);
			}
			else
				--i;
		}
		//排序
		sort(group.begin(), group.end(), [](const citem& t1,const  citem& t2)->bool {
			return t1.good > t2.good;
		});
		//淘汰
		if (g%4==0)
		{
			group_set.clear();
			int kept = 0;
			for (auto p = group.begin(); p != group.end() && kept < S; ++p)
			{
				if (group_set.find(*p) == group_set.end())
				{
					new_group.push_back(*p);
					group_set.insert(*p);
					++kept;
				}
			}
			group = new_group;
		}
		//输出
		cout << "Iter " << g << ":";
		group.begin()->output();

	}

	delete[] data;
	data = nullptr;
	return 0;
}