combinatorial number system encoder/decoder

test_singleset.d

import ae.utils.meta;

R binomialCoefficient(T, R=T)(T n, T m)
{
	if (n < m)
		return R(0);
	R result = 1;
	foreach (i; n - m + 1 .. n + 1)
		result *= i;
	foreach (i; 1 .. m + 1)
		result /= i;
	return result;
}

unittest
{
	assert(binomialCoefficient(3067L, 3) == 4803581405);
}

unittest
{
	import std.bigint : BigInt;
	assert(binomialCoefficient!(int, BigInt)(3067, 3) == 4803581405);
}

R multisetCoefficient(T, R=T)(T n, T k)
{
	return binomialCoefficient!(T, R)(n + k - 1, k);
}

unittest
{
	assert(multisetCoefficient(3067L, 3) == 4812987894);
}

import std.stdio;

/// Combinatorial number system encoder/decoder
/// https://en.wikipedia.org/wiki/Combinatorial_number_system
struct CNS(
	/// Type for packed representation
	P,
	/// Type for one position in unpacked representation
	U,
	/// Number of positions in unpacked representation
	size_t N,
	/// Cardinality (maximum value plus one) of one position in unpacked representation
	U unpackedCard,
	/// Produce lexicographic ordering?
	bool lexicographic,
	/// Are repetitions representable? (multiset support)
	bool multiset,
)
{
static:
	/// Cardinality (maximum value plus one) of the packed representation
	static if (multiset)
		enum P packedCard = multisetCoefficient(unpackedCard, N);
	else
		enum P packedCard = binomialCoefficient(unpackedCard, N);
	alias Index = P;

	private P summand(U value, Index i)
	{
		static if (lexicographic)
		{
			value = cast(U)(unpackedCard-1 - value);
			i = cast(Index)(N-1 - i);
		}
		static if (multiset)
			value += i;
		return binomialCoefficient(value, i + 1);
	}

	P pack(U[N] values)
	{
		P packed = 0;
		foreach (Index i, value; values)
		{
			static if (!multiset)
				assert(i == 0 || value > values[i-1]);
			else
				assert(i == 0 || value >= values[i-1]);

			packed += summand(value, i);
		}

		static if (lexicographic)
			packed = packedCard-1 - packed;
		return packed;
	}

	U[N] unpack(P packed)
	{
		static if (lexicographic)
			packed = packedCard-1 - packed;

		void unpackOne(Index i, ref U r)
		{
			bool checkValue(U value, U nextValue)
			{
				if (summand(nextValue, i) > packed)
				{
					r = value;
					packed -= summand(value, i);
					return true;
				}
				return false;
			}

			// TODO optimize: rolling product or binary search?
			// TODO optimize: don't check below N-i
			static if (lexicographic)
			{
				foreach_reverse (U value; 0 .. unpackedCard)
					if (checkValue(value, cast(U)(value - 1)))
						break;
			}
			else
			{
				foreach         (U value; 0 .. unpackedCard)
					if (checkValue(value, cast(U)(value + 1)))
						break;
			}
		}

		U[N] values;
		static if (lexicographic)
			foreach         (Index i, ref r; values)
				unpackOne(i, r);
		else
			foreach_reverse (Index i, ref r; values)
				unpackOne(i, r);

		return values;
	}
}

void main()
{
	static foreach (lexicographic; [false, true])
	static foreach (multiset; [false, true])
	{{
		writefln("===== lexicographic: %s, multiset: %s =====", lexicographic, multiset);
		alias testCNS = CNS!(uint, ubyte, 3, 10, lexicographic, multiset);
		alias pack = testCNS.pack;
		alias unpack = testCNS.unpack;
		[3, 5, 7].I!pack.writefln!"Packed: %d";
		[3, 5, 7].I!pack().I!unpack.writefln!"Re-unpacked: %s";

		import std.stdio : writefln;
		uint counter;
		foreach (ubyte a; 0 .. 10)
		foreach (ubyte b; cast(ubyte)(a + (multiset ? 0 : 1)) .. 10)
		foreach (ubyte c; cast(ubyte)(b + (multiset ? 0 : 1)) .. 10)
		{
			ubyte[3] input = [a, b, c];
			auto packed = testCNS.pack(input);
			auto unpacked = testCNS.unpack(packed);
			writefln("%s -> %3d -> %s", input, packed, unpacked);
			assert(packed < testCNS.packedCard);
			static if (lexicographic)
				assert(counter == packed, "Packed is wrong");
			assert(input == unpacked, "Unpacked is wrong");
			counter++;
		}
	}}
	writefln("correct horse battery staple");
	// foreach (n; 0 .. 220)
	// 	writeln(multisetUnpack!(ubyte, 10, 3)(n));
}