Flaschenzug.cpp

/*
Current implemenetation (v4):
Based on version 3:
- combines the equal calculations between parameters into a single calculation and therefore has to calculate a lot less
- Computational time: O(k*N) (loop -> ( std::partial_sum, loop ) ) ( + sort O(k*log(k)), k is usually a lot smaller than N so that doesn't matter)
- Memory: O(N+k) (a lot of data can be ignored while going on)
- boils down to adding a lot of numbers repeatedly together
- code becomes totally unclear and unintuitive, but works extremely quickly
- slightly optimized for sorted input (see constructor)
- two container optimization removed, it wasn't doing anything anymore, other than adding complexity
- there is nearly no parallelization potential anymore, but that is because all the things that could be calculated in parallel before are now done at once
*/
BigUnsigned Flaschenzug::Flaschenzug::GetNumberOfPermutationsInternalIterative(uint_fast32_t items)
{
	uint_fast32_t numContainers = containers.size();
	//these are the combined capacities of the containers beginning at every index
	std::vector<uint_fast32_t> combinedRestContainerCapacities(numContainers);
	std::partial_sum(containers.rbegin(), containers.rend(), combinedRestContainerCapacities.begin());
	//only two rows of item parameters are needed because the dependencies are always exactly one container down
	std::array<std::vector<BigUnsigned>, 2> resultsVectors{};
	resultsVectors.fill(std::vector<BigUnsigned>(items + 1, 1U));
	std::vector<BigUnsigned> *lastColumn = &resultsVectors[0], *currentColumn = &resultsVectors[1];

	//Last container gets implicitly calculated in the construction of the vectors
	//there is always only one way to arrange any amount of equal items in a single container
	if (numContainers <= 1) return 1U;

	for (int numContainersLeft = 2; numContainersLeft <= numContainers; ++numContainersLeft)
	{
		//this is the index of the container currently examined
		uint_fast32_t containerIndex = numContainers - numContainersLeft;
		//this stores the capacity of all containers after the current one
		uint_fast32_t combinedRestContainerCapacity = combinedRestContainerCapacities[numContainersLeft - 2];
		//this calculates the highest items parameter needed from the last row (lower bound is always 0)
		uint_fast32_t highestNeededSum = std::min(items, std::max(combinedRestContainerCapacity, items - containers[containerIndex]));
		//this preemptively sums up all the entries from the last row
		std::partial_sum(lastColumn->begin(), lastColumn->begin() + highestNeededSum + 1, lastColumn->begin());
		for (int currentItems = 0; currentItems <= (int) items; ++currentItems)
		{
			//every entry in a row is the sum over a range of entries in the row before
			//the partial sums up to the upper bound - the sums to the lower bound give the sum over the desired range
			//it's like using the antiderivative to get the integral on a range
			uint_fast32_t lowerBound = currentItems - std::min((int) containers[containerIndex], currentItems);
			uint_fast32_t upperBound = clamp(combinedRestContainerCapacity, lowerBound, (uint_fast32_t) currentItems);
			(*currentColumn)[currentItems] = (*lastColumn)[upperBound] - (lowerBound == 0 ? 0 : (*lastColumn)[lowerBound - 1]);
		}
		//the newly calculated row is then used as the source for the next one
		std::swap(currentColumn, lastColumn);
	}
	//the last value in the row that just got calculated is the desired result
	return (*lastColumn)[items];
}