c++algorithmdistributionc++23

How do I accurately distribute the numbers 1-100 (inclusive) between a weighted list <= 100 long?


I have a list of items, each item has a weight;

std::vector<float> weights{0.5, 2, 5};

this list is at most 100 items long, and at least 2 items long.

I want to inversely proportionately distribute the whole numbers 1-100 (inclusive) across this list so that the lowest weight receives the biggest range.

This code gets me close, but the ranges are not inversed:

    #include <iostream>
#include <vector>
#include <iomanip>

void distributeNumbers(const std::vector<float>& numbers) {
    float total = 0;
    for (float num : numbers) {
        total += num;
    }

    int start = 1;
    int end = 100;
    std::cout << "Distributing numbers from 1 to 100 based on proportions:" << std::endl;

    for (int i = 0; i < numbers.size(); ++i) {
        float number = numbers[i];
        
        // Calculate the range length for this number
        double proportion = static_cast<double>(total-number) / total;
        int rangeLength = static_cast<int>(proportion * 100);

        // Ensure we don't assign a range of zero length
        if (i == numbers.size() - 1) {
            rangeLength = end - start + 1;
        }

        int currentEnd = start + rangeLength - 1;
        std::cout << number << ": " << start << "-" << currentEnd << std::endl;

        // Update the start for the next number
        start = currentEnd + 1;
    }
}

int main() {
    std::vector<float> numbers = {9, 4, 3, 11, 7, 19, 3};  // Example input: numbers = {6, 2, 2}
    
    distributeNumbers(numbers);
    return 0;
}

When I say inversely proportional, I mean:

For an input such as:

weights{2, 1}

the output should be something like:

1-33
34-100

and an input such as:

weights{3,1}

the output would be something like:

1-25
26-100

and

weights{2,1,1}

would output

1-25
26-63
64-100

Solution

  • Since the math seems to be the problem, I'll skip the C++ part.

    You first transform your weights w={1.0, 2.0, 0.25} into inverse weights iw={1.0, 0.5, 4.0}. Reject any input <=0.0

    You then scale the inverse weights so they add up to 100. I.e. scale=100/(1.0+0.5+4.0) = 18.18181818.

    That means the length of each range is now just iw*scale={18, 9, 72} (rounded down). You'll notice you're missing one here: 1-18, 19-27, 28-99. In this easy case you know to add 1 to the biggest range, but in general you need to figure out if your specific use case has a hard requirement for this sort of rounding.