Function permutation_calculation

src/library/generator.transpose.cpp:363–420

calculate the permutation cycles consumed in swap kernels. each cycle is strored in a vecotor. hopfully there are mutliple independent vectors thus we use a vector of vecotor */

each cycle is strored in a vecotor. hopfully there are mutliple independent vectors thus we use a vector of vecotor
*/
void permutation_calculation(size_t m, size_t n, std::vector<std::vector<size_t> > &permutationVec)
{
	/*
	calculate inplace transpose permutation lists
	reference:
	https://en.wikipedia.org/wiki/In-place_matrix_transposition
	and
	http://www.netlib.org/utk/people/JackDongarra/CCDSC-2014/talk35.pdf
	row major matrix of size n x m
	p(k) = (k*n)mod(m*n-1), if 0 < k < m*n-1
	when k = 0 or m*n-1, it does not require movement
	*/
	if (m < 1 || n < 1)
		return;

	size_t mn_minus_one = m*n - 1;
	//maintain a table so check is faster
	size_t *table = new size_t[mn_minus_one + 1]();//init to zeros
	table[0] = 1;

	for (size_t i = 1; i < mn_minus_one; i++)
	{
		//first check if i is already stored in somewhere in vector of vectors
		bool already_checked = false;
		if (table[i] >= 1)
			already_checked = true;
		if (already_checked == true)
			continue;

		//if not checked yet
		std::vector<size_t> vec;
		vec.push_back(i);
		table[i] += 1;
		size_t temp = i;

		while (1)
		{
			temp = (temp*n);
			temp = temp % (mn_minus_one);
			if (find(vec.begin(), vec.end(), temp) != vec.end())
			{
				//what goes around comes around and it should
				break;
			}
			if (table[temp] >= 1)
			{
				already_checked = true;
				break;
			}
			vec.push_back(temp);
			table[temp] += 1;
		}
		if (already_checked == true)
			continue;
		permutationVec.push_back(vec);
	}
	delete[] table;
}