C++ version of multi-set ranking for small multisets

gistfile1.txt

#pragma once
#include "stdafx.h"

namespace multiset {
	typedef uint8_t byte;

	class FindMultisetRank
	{
	private:

		std::vector<int> m_typeCount;
		int m_types;
		int m_length;
		int m_maxPotential;
		int m_maxTypeLength;

	public:

		FindMultisetRank(const std::vector<int>& baseSet)
		{
			m_length = baseSet.size();
			int last = 0;
			m_types = 1;
			for (int i = 0; i < baseSet.size(); i++)
			{
				if (last != baseSet[i])
				{
					last = baseSet[i];
					m_types++;
				}
			}

			//count each type
			m_typeCount = std::vector<int>(m_types);
			last = baseSet[0];
			for (int i = 0; i < baseSet.size(); i++)
			{
				int type = baseSet[i];
				if (last != baseSet[i])
				{
					last = baseSet[i];
				}
				m_typeCount[type]++;
				if (m_maxTypeLength < m_typeCount[type]) m_maxTypeLength = m_typeCount[type];
			}

			computePotential();
		}

		std::vector<int> unRank(int permutationIndex)
		{
			if (permutationIndex < 0 || permutationIndex >= m_maxPotential)
				throw std::exception("Index is beyond permutation bounds.");

			std::vector<int> result = std::vector<int>(m_length);
			std::vector<int> currentCounts = m_typeCount;//copy
			int currentPotential = m_maxPotential;
			int currentLength = m_length;

			// For each position...
			for (int position = 0; position < m_length; position++, currentLength--)
			{
				// Compute selector, which is just rank reduced to be in range of current length of multiset.
				int selector = ((permutationIndex * currentLength) / currentPotential);
				int offset = 0;
				byte type = 0;

				// Note that: 
				//  - Sum of count of all currenttly remaining types is length of multiset.
				//  - Current potential is sum of potentials of sub-multisets.
				// Scan for offset of sub-multiset in which range selector could be found.
				while ((offset + currentCounts[type]) <= selector)
				{
					offset += currentCounts[type];
					type++;
				}

				// Remove consumed offset.
				permutationIndex -= (currentPotential * offset) / currentLength;
				// Compute potential of sub-multiset.
				currentPotential = currentPotential * currentCounts[type] / currentLength;
				// Consume type.
				currentCounts[type]--;
				// Store chosen type.
				result[position] = type;
			}

			return result;
		}

		int findRank(std::vector<int> multiset)
		{
			if (multiset.size() != m_length)
				throw new std::exception();

			int result = 0;
			int currentPotential = m_maxPotential;
			int currentLength = m_length;
			std::vector<int> currentCounts = m_typeCount;

			// for each position
			for (int position = 0; position < m_length - 1 && currentPotential > 1; position++, currentLength--)
			{
				int offset = 0;
				byte type = (multiset[position]);

				// computing sum of potentials for each sub-multiset which has lower index than selected type
				for (int i = 0; i < type; i++)
				{
					offset += currentCounts[i];
				}

				// add offset to the rank/result
				result += (currentPotential * offset) / currentLength;
				// compute potential of sub-multiset
				currentPotential *= currentCounts[type];
				currentPotential /= currentLength;
				// consume type
				currentCounts[type]--;
			}

			return result;
		}

		int getMaxPotential()
		{
			return m_maxPotential;
		}

	private:

		static long findFactorial(int n)
		{
			int fact = 1;
			for (int i = 2; i <= n; i++)
			{
				fact *= i;
			}

			return fact;
		}

		void computePotential()
		{
			long res = findFactorial(m_length);
			for (int t = 0; t < m_types; t++)
			{
				res /= findFactorial(m_typeCount[t]);
			}
			m_maxPotential = (int)res;
		}
	};
}