How to efficiently generate, in C, x random numbers in a given interval such the sum is constant?-CodePudding

To randomly generate nbValue in the interval [average-delta,average delta] such that the sum of these values is equal to fullSum, I use this program
1 : nbValue-1 are randomly generated
2 : the last value is calculated (fullSum - Sum of nbValue)
3 : If the last value is not in the interval, this loop is restarted.

This is the code :

int main()
{

    int fullSum = 4096, nbValue = 16;
    int average = round(fullSum / nbValue);
    int delta = round(average*0.125);
    int tryCounter = 0;
    int lastStep;

    srand(time(0));

    do {
      int currentSum = 0;
      for (int i=0;i<nbValue-1;i  )
        currentSum =rand()%(delta*2 1)-delta average ;
      tryCounter   ;
      lastStep = fullSum - currentSum;
    }
    while ( (lastStep < average - delta) || (lastStep > average   delta) );

    printf("Total tries : %d\n",tryCounter);
}

Is there a better solution to be more efficient (That means, to reduce the number of tries) ? (Rq : I want a uniform distribution on the intervall)

Thanks for answer.

CodePudding user response：

One possible improvement (depends of cost of check vs. cost of rand()):

Rather than iterate nbValue-1 times and then check if a possible solution exist, also check after each iteration.

  // Re-start here
  sum = 0; 
  for (int i=0; i < nbValue-1; i  ) {
    currentSum  = rand()%(delta*2 1)-delta average ;       
    int diff = (fullSum - currentSum)/(nbValue - i - 1);
    if (diff < average - delta) || (diff > average   delta) {
      start for loop again
    }
  }  
  ...

CodePudding user response：

I came up with a tail-recursive solution that "almost" works :-)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int rand_between(int lo, int hi) {
    // simple implementation may suffer from bias
    return rand() % (hi - lo   1)   lo;
}

void rand_with_const_sum(int *a, int n, int sum, int min, int max) {
    if (n-- == 0) return;
    int tmpmax = sum - n*min;
    int tmpmin = sum - n*max;
    if (tmpmax > max) tmpmax = max;
    if (tmpmin < min) tmpmin = min;
    a[0] = rand_between(tmpmin, tmpmax);
    rand_with_const_sum(a   1, n, sum - a[0], min, max);
}

int main(void) {
    srand((unsigned)time(0));
    int a[100];

    rand_with_const_sum(a, 10, 100, 7, 13);
    for (int i = 0; i < 10; i  ) printf("%d ", a[i]); puts("");

    puts("");

    rand_with_const_sum(a, 100, 1000, 7, 13);
    // shuffle(a, 100); // ?
    for (int i = 0; i < 100; i  ) printf("%d ", a[i]); puts("");

    return 0;
}