How to distribuite a value unequally?

Lexyth · November 30, 2018, 10:35am

Hey, so distributing a value equally is just 50/5 = 5 Times a 10 value, But i Would Need a result of something like {15, 5, 20, 7, 3}. Now, i technically know how to do this in Code, But it‘s not very efficient, so i was wondering if there is a built in or other more efficient method, than just dividing the value by the amount of values you want, randomly increasing one and the others decreasing by the Same Divided by how many are left. In code this looks like this :

void calculate() {
  float a = 100;
  float[] b = new float[5];
  for (int i = 0; i < b.length; i++) {
    b[i] = a/b.length;
  }
  for (int i = 0; i < b.length; i++) {
    float r = random(-100, 100);
    b[i] += r;
    for (int j = 0; j < b.length; j++) {
      if (i != j) b[i] -= r/b.length-1;
      //or
      b[i] -= r/b.length; //has the Same result, if i recall right
    }
  }
}

The Second for loop is what Takes away a lot of Time, because i Need to do it very often. Also, it should change the values randomly, not set them, so that you could change by how much they are changed, while setting them randomly Would just give completely random values.

hamoid · November 30, 2018, 10:43am

Something in this direction?

float values[] = new float[5];
float desiredSum = 50;
float sum = 0;
for(int i=0; i<values.length; i++) {
  values[i] = random(100);
  sum += values[i];
}
float k = sum/desiredSum;
for(int i=0; i<values.length; i++) {
  values[i] /= k;
  println(i, round(values[i]));
}

It’s not perfect, because the sum can be 51 because of rounding. No time to figure that out now, but maybe it gets you started

quark · November 30, 2018, 11:02am

It would be useful to create a function to do this and also specify the maximum size of any single value like this

int[] parts;

void setup() {
  parts = distribute(50, 40);
  printArray(parts);
}

/**
 Create an array whose values add up to
 'total' but whose individual values don't
 exceed 'max_part'
 */
int[] distribute(int total, int max_part) {
  IntList list = new IntList();
  int sum = 0;
  while (sum != total) {
    int part = int(1 + random(0, max_part));
    if (part > total - sum) {
      part = total - sum;
    }
    list.append(part);
    sum += part;
  }
  return list.array();
}

if max_part equals total then it is possible to get a single element array.

hamoid · November 30, 2018, 11:28am

Nice approach, but in this case you don’t know how many values you will get right? I assumed a fixed number of values was expected.

hamoid · November 30, 2018, 12:21pm

The code I posted above had an issue: the added values could be above or below the requested total. The way I figured this out was something I often do in cases like this: open a spreadsheet in LibreOffice and try to visualize the problem with a bunch of numbers. Then I adjust the formulas in the spreadsheet until I get what I want, and finally move those formulas back to the program.

It looks like this now:

void setup() {
  frameRate(5);
}
void draw() {
  int[] nums = getDist(5, 50);
  
  // just to make sure, add them up to check
  // if the result is correct
  int sum = 0;
  for(int i=0; i<5; i++) {
    sum += nums[i];
  }
  println(nums);
  println("sum: ", sum);
  println();
}
int[] getDist(int count, int reqSum) {
  // create a list of random numbers
  // and calculate their sum
  float values[] = new float[count];
  float fSum = 0;
  for (int i=0; i<count; i++) {
    values[i] = random(100);
    fSum += values[i];
  }
  // this factor tells us by how much we
  // need to divide the random numbers
  // so they add exactly up to the requested sum
  float k = fSum/reqSum;
  
  // figure out the integer values so they add up
  // to reqSum. We need to keep track of the
  // sum as float and as integer to round the difference.
  // this way we don't accumulate error because we work
  // with the sum, we don't round the individual random
  // number.
  fSum = 0;
  int iSum = 0;
  int result[] = new int[count];
  for (int i=0; i<count; i++) {
    values[i] /= k;
    fSum += values[i];
    result[i] = round(fSum - iSum);
    iSum += result[i];
  }
  return result;
}

It shows something like this:

[0] 15
[1] 4
[2] 11
[3] 2
[4] 18
sum:  50

[0] 15
[1] 9
[2] 10
[3] 12
[4] 4
sum:  50

[0] 7
[1] 9
[2] 20
[3] 3
[4] 11
sum:  50

quark · November 30, 2018, 12:34pm

That is a bit more challenging since I assume the OP wants no zeroes.

So I started with the fixed size array filled with 1’s and then tried different approaches
A) randomly adding 1 to a random element in the array but all the values tended towards the average.
B) randomly adding a random value of the remaining amount to a random element in the array. This filled the array too quickly leaving a lot of 1’s
C) same as (B) but the amount added was randomised from a much smaller number resulting in more iterations of the loop but a better distribution

int[] parts;

void setup() {
  parts = distribute(100, 8);
  printArray(parts);
}

/**
 Create a fixed size array (nbr_parts) and fill with values
 that add up to 'total'.
 */
int[] distribute(int total, int nbr_parts) {
  float delta = 3 + total/(3.14159 * nbr_parts); 
  int[] array = new int[nbr_parts];
  for (int i = 0; i < array.length; i++) {
    array[i] = 1;
  }
  int sum = array.length;
  while (sum != total) {
    int part = int(1 + random(delta));
    if (part > total - sum) {
      part = total - sum;
    }
    int partIdx = int(random(array.length));
    array[partIdx] += part;
    sum += part;
  }
  return array;
}

[0] 8 [1] 4 [2] 16 [3] 7 [4] 15 [5] 18 [6] 19 [7] 13

hamoid · November 30, 2018, 12:42pm

Very interesting Little changes to the rules completely change the algorithms. Also interesting how we humans assume different meanings.

I show here what I meant with using a spreadsheet to help me “compute the problem in the brain” step by step.

2018-11-30-134030_598x426_scrot

ps. I should have added that k = desired sum / sum of the above

quark · November 30, 2018, 12:55pm

Devising algorithms for problems like this makes programming exciting / interesting / fun. Perm any combination of adjectives.
Often problems are ill-defined so that we have to make assumptions, of course the word assume comes from

making an ASS of U and ME

Having made many assumptions in my life and on this forum I am off to do some braying…

Hee haw, hee haw …

Lexyth · November 30, 2018, 1:29pm

Oh wow, didn‘t expect so many answers in such a short Time .
Guess it‘s my fault for not explaining better what i Need .

The code i posted as an example is actually all i Need, so to just distribute an int across an array (or more specifically, to distribute 1 or 100 to get a percentage).
And the values don‘t Need to be smaller than another value, as Long as they add up to exactly 1/100 without problems and are smaller than that, so no negative numbers should be in it (Though i think that Would just make it more complicated anyway) .

So the code i posted was what i Need, But i wanted to know if there was a better way to do it (Performance wise(is „wise“ rights?)) or an already inbuilt function for it, or something like that.
Basically anything that Makes an equal array that adds up to 1 or 100 (like 25,25,25,25) become (10,30,55,5).
And then (might Need a different method for this, Even if just for Performance reasons) i‘d Need (10,30,55,5) be changed to (lets say i want the 2nd element to become bigger) (9,33,54,4).

So just what my code above does in one go (Or if you take the first loop as creating the (25…) array and the second as changing it to (29,26,23,22).
And then slowly make it adapt further.
Thats the best i can describe it as, sorry

Also, i do something similar like a spreadsheet with desmos. That’s how i came up with the method i posted in my question

Again, sorry for the Badly explained question

quark · November 30, 2018, 3:30pm

I see a lot of questions like this forum about improving performance and generally they mean either

can I do it faster? or
can I do it with less program code?

Using an inbuilt function will certainly use less code but it doesn’t mean it can be done faster! It all depends on the algorithm used.

I once created a sketch to visualise a wide range of sort algorithms (about 17 I think) some were faster, some used less memory, some better for huge data sets etc. but which is better. There is no simple answer because different end users have different requirements. For instance the original Quicksort algorithm when applied to a large already sorted array would take an eternity to stop where the humble Bubble sort would take next to no time. Start with randomised data and the Quicksort outperforms the Bubble sort by many orders of magnitude.

Some people like to perform a task with as few program statements as possible, in fact there used to be one forum contributor that sometimes posted the most unintelligible code I ever saw. It looked like it had been deliberately obfuscated. Even I, with decades of programming experience struggled to understand how the code worked and this would have been an answer to a beginner.

Generally the obfuscated code was no faster than longer, clearer code. The reason being that the Java compiler will analyse and perform some optimisation on your code but even better, your compiled code is further optimised at runtime by the JVM.

So go for a well designed algorithm then convert it simple, well commented understandable code. Let the compiler and JVM do the rest.

I am a great believer in the KISS principle - Keep It Simple Stupid

Lexyth · November 30, 2018, 6:06pm

Yeah, i know that short code doesn‘t mean fast performance, But in general the inbuilt code is better than what i do, and it‘s made to be the best solution for what it should do (which also means that it‘s slower if it Takes more options into account).

So yeah, Even if the code is longer, i Need something that does what i mentioned in the Post above as fast as possible, or at least the confirmation that my code is pretty close to the best it can get and changes wouldn‘t really do much. (Maybe save 1 millisecond every 10bilion iterations or so).

jeremydouglass · December 3, 2018, 9:57pm

There are a lot of interesting cases, such as more bins than sum, more range than sum, only one bin, etc etc.

For most of those, the solution is to allow numbers to go negative in order to satisfy the constraints of the distribution asked for. So, if I ask for two bins with a sum of 0 and a random range of 10, then {-5, 5} would be a valid solution. For efficiency 1 bin and 0 bins are special cases.

My general approach would be a three-pass solution.

pre-populate the array with the mean. There may be leftover, but we can anticipate exactly how many cells will be mean+1 in a single pass.

  int mean = sum/binCount;
  int left = sum%binCount;
  for(int i=0; i<binCount; i++){
    bins[i] = i<left ? mean+1 : mean;
  }

iterate over pairs, and carry value between them, conserving the sum. The list sum is valid when this loop starts, and after each operation it is still valid – one entry goes up, the other goes down.

  for(int i=1; i<binCount; i=i+2){
    int alloc = (int)random(-carry, carry+1);
    bins[i-1] = bins[i-1] - alloc;
    bins[i] = bins[i] + alloc;
  }

optionally, shuffle the result – this will produce many potential orders that would not be possible from pairs.

return shuffleIntArray(bins);

What I like about this is that it is reasonably quick and really robust – you can throw anything at it and it produces a reasonable output from the space of all possible solutions, and it could produce (I believe) any possible solution to a given request for a distribution.

void setup() {
  println(binify(20, 5, 1));
  println(binify(20, 5, 5));
  println(binify(20, 5, 10));
  println(binify(20, 5, 20));
  println(binify(20, 5, 100));
  println(binify(20, 5, 0));

  println(binify(5, 5, 1));
  println(binify(5, 5, 2));
  println(binify(5, 5, 5));
  println(binify(5, 5, 10));
  println(binify(5, 5, 0));

  println(binify(0, 5, 10));
  println(binify(0, 5, 2));
  println(binify(0, 5, 0));
  
  println(binify(10, 1, 100));
  println(binify(10, 0, 0));
}

int[] binify (int sum, int binCount, int carry) {
  println("binify: sum ", sum, " binCount ", binCount, " carry ", carry);
  if(binCount==0) return null;
  if(binCount==1) return new int[]{sum};
  int[] bins = new int[binCount];
  int mean = sum/binCount;
  int left = sum%binCount;
  for(int i=0; i<binCount; i++){
    bins[i] = i<left ? mean+1 : mean;
  }
  for(int i=1; i<binCount; i=i+2){
    int alloc = (int)random(-carry, carry+1);
    bins[i-1] = bins[i-1] - alloc;
    bins[i] = bins[i] + alloc;
  }
  return shuffleIntArray(bins);
}

int[] shuffleIntArray (int[] list) {
  IntList shuffler = new IntList(list);
  shuffler.shuffle();
  for (int i=0; i<list.length; i++) {
    list[i] = shuffler.get(i);
  }
  return list;
}

To speed it up you could drop the shuffling step – that will constrain the output, but it will still appear semi-random for some purposes.

You might also be able to squeeze some more speed out by combining steps 1 and 2 into a single for loop.

Lexyth · December 4, 2018, 2:24pm

Thanks
But apparently i‘m expressing myself kinda wrong
What i Need is pretty much just the code i posted, But made more efficient (Or the Information that that is already as good as it gets). To be more specific, the Second for loop in the code. So this one :

float[] arr = new float[100];

void setup() {
  for (int i = 0; i < arr.length; i++) {
    arr[i] = 1/arr.length;
  }
  for (int i = 0; i < arr.length; i++) {
    distribute(random(0, arr.length), random(-0.1, 0.1));
  }
}

void mousePressed() {
distribute(random(0,arr.length), random(-0.01, 0.01));
}

void distribute(int n, float value) {
  arr[n] += value;
  for (int i = 0; i < arr.length; i++) {
    arr[i] -= value/arr.length;
  }
}

Thats basically all i Need, But it‘s very Slow When there are 1000+ Elements in the array, and i have 1000+ arrays in my program… so that Makes it very Slow…

GoToLoop · December 4, 2018, 3:08pm

static final void distribute(final int idx, final float val, final float[] arr) {
  final int len = arr.length;
  final float valByLen = -val/len;

  arr[idx] += val;

  for (int i = 0; i < len; arr[i++] += valByLen);
}

hamoid · December 4, 2018, 3:32pm

For better performance you should avoid nested loops. The code I posted above does the work between 10 and 15 times faster for 1000 entries, 30 times faster for 2000 entries.

It’s about having the complexity be linear instead of quadratic or exponential.

Lexyth · December 4, 2018, 6:17pm

Thanks that‘s exactly what i was looking for

Lexyth · December 4, 2018, 6:27pm

Thanks, i didn‘t know that that Would make such a difference i kinda thought that it would somehow rearrange it behind the scene to become linear somehow, though now that sounds like pretty wishful thinking . Also, in case of your first answer, it would have replaced each value with a random number each Time i call it, and although i could just have removed the first part, i didn‘t know where to get a replacement for the k Variable

In any case, GoToLoop‘s answer is exactly what i was looking for, so i‘ll take that.

Thanks to all, for all the effort

(Btw, i feel like i sound pretty demanding, so if it Sounds like that, it‘s not meant that way )

starkid · December 4, 2018, 10:30pm

Hey I’m new to posting questions here and I notice that every time you do something to my question I get a notification with a pencil on it and then when I open it I see my question on the left and then the same thing on the right again. Does that mean you changed something or answered my question? Please let me know thanks.

hamoid · December 5, 2018, 12:08pm

Ha. Funny, I assumed you wanted integers because in your initial example you wrote {15, 5, 20, 7, 3} (even if the code in that example included a float array). With floats is much simpler And good that you got what you needed!

Topic		Replies	Views
Thoroughly seeding random() Coding Questions	4	286	September 12, 2020
Uneven distrobution instead of normal map() Coding Questions	3	618	November 21, 2018
Randomly distribute objects on grid Coding Questions	4	1651	December 23, 2019
How to calculate two different mean values with the same function Coding Questions	7	895	January 21, 2019
New to Arrays, help making a simple less than 10 lines code Beginners	3	251	November 5, 2023

How to distribuite a value unequally?

Related topics