[SOLVED] Best way to evenly distribute integer variables on fluctuating input

Kustom42 · 05-08-2013, 05:35 PM

Ok,

So here's what I'm doing and what I'm trying to do:

Using bash I have a variable that counts up a total number of items. Lets call it $TOTAL

I also many variables for different days of the week and other variables:

Code:

$100SUN
$100MON
$100TUE
$100WED
$100THUR
$100FRI
$100SAT

$101SUN
$101MON
$101TUE
$101WED
$101THUR
$102FRI
$102SAT

All of the variables are integers.

The integers will change frequently and this script will need to work to evenly distribute the $TOTAL integer across the other variables to keep them as even as possible.

So lets say for example:

Code:

$TOTAL=20 # This isn't how it is actually determined just for example purposes

$100SUN=29
$100MON=30
$100TUE=28
$100WED=19
$100THUR=19
$100FRI=26
$100SAT=16


$101SUN=29
$101MON=30
$101TUE=30
$101WED=30
$101THUR=23
$102FRI=26
$102SAT=21

So in the above example, I have 20 to distribute and I want to try and keep it as even as possible. So my result would be:

Code:

$100SUN=29
$100MON=30
$100TUE=28
$100WED=24 # Add 5 Here
$100THUR=24 # Add 5 Here
$100FRI=26
$100SAT=24 # Add 8 here


$101SUN=29
$101MON=30
$101TUE=30
$101WED=30
$101THUR=23
$102FRI=26
$102SAT=23 # Add 2 here

It does not have to be an exact science but due to the amount these numbers fluctuate it could be that $100SUN has 30 this week and 20 next week so I need to be able to identify the lowest variables and add them out to keep it well balanced.

I'm just trying to figure out the best way to skin the cat here as I'm not the best math person.

grail · 05-09-2013, 11:14 AM

You have shown what you started with and what you would like in the end, but I see no clear explanation as to why you chose the entries to be changed or how you chose how much to add to each entry?

So questions are:

1. How did you choose the value of 24 for the first group and 23 for the second to be the amount to increase the other values to?

2. What would happen if all values were equal, ie all $100XXX = 25, do any of them get changed?

I think you need to ask yourself these and other questions on the how before we can provide answers.

Kustom42 · 05-09-2013, 08:43 PM

Yes they will change every time the script runs. Thats the part that is giving me trouble, if the values were static it wouldnt be an issue but they are the result of a query and will always be integers in the range of probably 10-50.

Also in this case I just manually evened them out based upon the lowest variables and the amount I had to add to them.

grail · 05-10-2013, 04:19 AM

So are you saying it is impossible to know what numbers we need to add and what numbers we will want to add to? If so, then the solution is just as impossible.

We will need some idea on how you would manually do what you need if we are gong to be able to automate it.

chrism01 · 05-10-2013, 04:40 AM

I'd express the output nums as fractions of eg 100 (%age) or fractions of eg the highest num in the set, then divide the fill-in total eg 20 into the same relative amts and add the highest 'fraction amt' of 20 to the smallest output and work along the (output) series from smallest to highest, adding successively smaller amts.

Any fraction of 20 < 1 is rounded down, so we only add to the lower outputs.

(NB: I haven't checked the logic/maths there, but I think you get my gist).

In other words, 'fractions' of 20 to add are inverse in size to the output amt they are being added to.

Kenhelm · 05-10-2013, 09:48 AM

This uses bash arrays. It goes through all of the DAYs twenty times. Each time it finds the current lowest number and adds one to it.

Code:

DAY[1001]=29
DAY[1002]=30
DAY[1003]=28
DAY[1004]=19
DAY[1005]=19
DAY[1006]=26
DAY[1007]=16

DAY[1011]=29
DAY[1012]=30
DAY[1013]=30
DAY[1014]=30
DAY[1015]=23
DAY[1016]=26
DAY[1017]=21

TOTAL=20
for (( i=1; i<=TOTAL; i++ ));do
  lowest=1001
  for n in {1001..1007} {1011..1017};do
    (( DAY[n] < DAY[lowest] )) && lowest=$n
  done
  (( DAY[lowest]++ ))
done

Code:

# Display the results
for n in {1001..1007} {1011..1017};do
  echo "DAY[$n]=${DAY[n]}"
done

DAY[1001]=29
DAY[1002]=30
DAY[1003]=28
DAY[1004]=24
DAY[1005]=24
DAY[1006]=26
DAY[1007]=24
DAY[1011]=29
DAY[1012]=30
DAY[1013]=30
DAY[1014]=30
DAY[1015]=23
DAY[1016]=26
DAY[1017]=23

Kustom42 · 05-10-2013, 01:51 PM

Quote:

Originally Posted by Kenhelm

This uses bash arrays. It goes through all of the DAYs twenty times. Each time it finds the current lowest number and adds one to it.

Code:

DAY[1001]=29
DAY[1002]=30
DAY[1003]=28
DAY[1004]=19
DAY[1005]=19
DAY[1006]=26
DAY[1007]=16

DAY[1011]=29
DAY[1012]=30
DAY[1013]=30
DAY[1014]=30
DAY[1015]=23
DAY[1016]=26
DAY[1017]=21

TOTAL=20
for (( i=1; i<=TOTAL; i++ ));do
  lowest=1001
  for n in {1001..1007} {1011..1017};do
    (( DAY[n] < DAY[lowest] )) && lowest=$n
  done
  (( DAY[lowest]++ ))
done

Code:

# Display the results
for n in {1001..1007} {1011..1017};do
  echo "DAY[$n]=${DAY[n]}"
done

DAY[1001]=29
DAY[1002]=30
DAY[1003]=28
DAY[1004]=24
DAY[1005]=24
DAY[1006]=26
DAY[1007]=24
DAY[1011]=29
DAY[1012]=30
DAY[1013]=30
DAY[1014]=30
DAY[1015]=23
DAY[1016]=26
DAY[1017]=23

Maybe I'm missing something here but it looks like you are just using brace expansion and looping through? This doesnt look like it does much for me but I could be mis-reading it.

I have made some progress, based upon some other posts I found online of similar problems I created a function which will sort my arrays but am I having trouble identifying which particular one is which after it is sorted:

Code:

sort_array()
{
    # usage: sort_array <array_size> <array>
    if ((! $#)); then # This checks to make sure the above arguements exist or will exit the script if they dont
        return 1
    fi

    local arr_size=$1 # Set a variable that is local to this function for the size of the array
    shift
        
    set -f; local arr=($@); set +f
    local _permut=1 _tmp i


    while ((_permut)); do
        _permut=0

        for ((i = 0; i < arr_size - 1; i++)); do
            if ((arr[i + 1] < arr[i])); then
                _tmp=${arr[i]}
                arr[i]=${arr[i + 1]}
                arr[i + 1]=$_tmp

                _permut=1
            fi
        done
    done

    echo "${arr[@]}"
}

Any thoughts on how I could figure out which one is which after the fact? Could I still do a simiar sort function if I changed the variables so they had a text string identifier like: 29_100_SUN?

I'm thinking I might be able to just add a cut statement to strip off the text then re-append it but not sure how to implement that exactly. Have been trying with a bit of trial and error.

Kustom42 · 05-10-2013, 01:59 PM

Quote:

Originally Posted by grail

So are you saying it is impossible to know what numbers we need to add and what numbers we will want to add to? If so, then the solution is just as impossible.

We will need some idea on how you would manually do what you need if we are gong to be able to automate it.

I am just taking this project over, it is something that I currently do manually every few days. I check to see if I have new systems to add, figure out how many I have, then figure out how many are already existing on my different proxies for the different days of the week and just try to evenly split them out the best I can. I just don't want one of my proxies to get 60 systems on one day and then 10 the next but if monday has 35 and tuesday has 30 its not a big deal.

I guess your post is the biggest thing that is giving me trouble, there are not enough static variables in the equation.

chrism01 · 05-13-2013, 01:14 AM

Kenhelm's soln makes good sense. He's just taken your stems eg 100, 101, ... and appended the day number of the day of the week, starting from 1. (sun=1, mon2, ..)
This gives a nice numeric sequence for his lists/loop.
The idea of just adding one to the lowest each time round the loop is great; simple but effective