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

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

• c++
• algorithm
• distribution
• c++23

• 1 The requirement here is a bit vague. I suspect you want something like {1.3, 1.3} => {1-50, 51-100}, {1.0, 2.0}=>{1-33,34-100} and {2.0, 1.0}=>{1-67,68-100}. That implies that the exact range depends on the order of the input, but the length of each range is determined solely by the relative fraction x[i]/sum(x) – MSalters Commented Jan 20 at 12:40
• Well, both 88-82 and 83-106 seem wrong too. – Bob__ Commented Jan 20 at 12:44
• @MSalters They mention "inversely proportionately", so they might want {1.0, 2.0}=>{1-67,68-100} and {2.0, 1.0}=>{1-33,34-100} instead. – Bob__ Commented Jan 20 at 12:50
• 3 Should we just transform weights[i] into 1/weigth[i] and use regular proportion? – Jarod42 Commented Jan 20 at 12:54
• 2 "I can't write the code to do maths I don't know" Imho you need to understand that is two seperate parts. Before you know what to implement, any code you write can only be wrong. You first need a clear idea of what you want to implement, and as long as that step isnt done, it is too early to write code. – 463035818_is_not_an_ai Commented Jan 20 at 13:09

2 Answers 2

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.

The inverse bit is a bit of a red herring. Solve the problem for non-inverse, and then invert.

Ie, instead of solving for

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

write an algorithm that solves for:

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

Then modify the algorithm to take a weight function. For each element, solve it for weight(elem). You can start with it being [](auto x){return x;} for initial testing, then do [](auto x){return 1./x;} to get you inverse weights.

Solving for the simpler case (simple weights) means you can fully test your algorithm without having to worry about inverses making it complicated. The linear weight with no transform algorithm can be written, tested, and polished; then adding the transform to it is another testing pass (and you keep the working version to compare it to).

...

To split a range by weight, first you add up all of the weights. Each one then gets weight(elem)/total_weight fraction of the elements.

A tricky part happens due to rounding; as you can only put integer numbers of elements in each element's bucket, determining how to do this requires a bit of extra thought.

I'd calculate weight(elem)/total_weight, and split that into the integer part and the fractional part. Add up the integer parts and find your remainder (out of 100). Say, you might have 12 parts remaining as the integer parts add up to 88.

Then sort the fractional parts and assign to the 12 largest fractional parts an extra integer part.

This minimizes the linear error in your output ranges.

Another option would be to minimize the multiplicative error in your output ranges. In this case, you'd assign any non-zero element weight at least 1 integer part (ie, round 0.000001 up to 1). This can result in negative "remainder".

Then assign the remainder, or extract extra elements, to the ones with the best (or worst) ratio.

The math here is harder, so just go for minimizing linear error.

...

So, to be clear, I'd propose doing it in a few passes to keep it simple.

First, map your elements to weights.

Second, normalize your weights to add up to 100.

Third, assign integer parts to each weight, and record fractional leftovers.

Forth, find the leftover weight (after integers), and assign them to the elements based on the fractional leftover size.

Fifth, turn these integer weights into ranges.

You can be slick and do this "in order", but by keeping each step simple you can test if the logic you wrote is correct, and even write simple unit tests.