Spreading value x randomly between x amount of elements

Started by
9 comments, last by Servant of the Lord 7 years, 10 months ago

Here's my approach. I shuffle the order the elements are visited, to alleviate bias towards the end of the vector.
(The bias is still there for whatever elements I give first shot at the values, but those elements are randomly distributed throughout the vector instead of grouped by order of first-come-first-serve)

I also applied a little (optional) fudgery to the maximum amount assigned each element, so the results aren't quite as extreme.


#include <iostream>
#include <vector>
#include <random> //For std::mt19937, std::random_device(), and std::uniform_int_distribution()
#include <algorithm> //For std::shuffle

void FillBuckets(std::vector<int> &buckets, const int amountToDistribute)
{
	std::mt19937 randomGenerator(std::random_device{}());
	
	//We generate some indices to fill the bucket elements in a random order.
	std::vector<size_t> bucketIndices(buckets.size());
	std::iota(begin(bucketIndices), end(bucketIndices), 0);
	std::shuffle(begin(bucketIndices), end(bucketIndices), randomGenerator);
	
	int bucketsRemaining = static_cast<int>(bucketIndices.size());
	int amountRemaining = amountToDistribute;
	
	for(size_t index : bucketIndices)
	{
		int amountToGive = 0;
		
		//If this isn't the last bucket, take a random amount of the remaining value.
		if(bucketsRemaining > 1)
		{
			//Balances out the numbers a bit more, so the first few buckets don't steal everything.
			//This means, if there are two buckets remaining, one of the buckets can take 100%.
			//If there are three buckets remaining, the most each bucket can take is 50%.
			//If there are four buckets remaining, the most each bucket can take is 33%, and so on.
			int maxToGive = (amountRemaining / (bucketsRemaining-1));
			amountToGive = std::uniform_int_distribution<int>(0, maxToGive)(randomGenerator);
		}
		//If this IS the last bucket, just take everything that remains.
		else
		{
			amountToGive = amountRemaining;
		}
		
		buckets[index] = amountToGive;
		amountRemaining -= amountToGive;
		
		bucketsRemaining--;
	}
}

int main()
{
	std::vector<int> buckets(10);
	FillBuckets(buckets, 100);
	
	std::cout << "Result: ";
	for(int amount : buckets)
	{
		std::cout << amount << " ";
	}
	std::cout << std::endl;
	
	return 0;
}

This topic is closed to new replies.

Advertisement