title: Weighted random number generation
body: <p>I would like to generate weighted random numbers in an exact manner. I can explain exact with an example: My input array is [1, 2, 3] and their weights are again [1, 2, 3]. In that case I expect to see 1 for 1 times, 2 for 2 times and 3 for 3. Like 3 -> 2 -> 3 -> 1 -> 3 -> 2...</p>
  
  <p>I am implementing random number generation with rand() to get a range between [0, sum_of_weights). sum_of_weights = 1 + 2 + 3 = 6 for the example above. I searched for existing solutions on the Internet, however the result is not what I want. Sometimes I got 2 more than 2 times and no 1 in the sequence. Its still weighted but not exactly give the number of times I waited for.</p>
  
  <p>I am not sure whats wrong with my code below. Should I do something wrong or I try totally different? Thanks for your answers.</p>
  
  <pre><code>int random_t (int items[], int items_weight[], int number_of_items)  
  {   
      double random_weight;  
      double sum_of_weight = 0;
      int i;
  
      /* Calculate the sum of weights */  
      for (i = 0; i &lt; number_of_items; i++) {
          sum_of_weight += items_weight[i];
      }
  
      /* Choose a random number in the range [0,1) */
      srand(time(NULL));
      double g = rand() / ( (double) RAND_MAX + 1.0 );
      random_weight = g * sum_of_weight;
  
      /* Find a random number wrt its weight */
      int temp_total = 0;
  
      for (i = 0; i &lt; number_of_items; i++) 
      {
              temp_total += items_weight[i];
  
              if (random_weight &lt; temp_total)
              {
                  return items[i];
              } 
      }   
          return -1; /* Oops, we could not find a random number */
  }
  </code></pre>
  
  <p>I also tried something different (the code is below). It worked for my case, but integer overflow and extensive use of static variables makes it problematic.</p>
  
  <p>If you enter an input array before give NULL and continue to work with it. A little bit similar to strtok() usage.</p>
  
  <pre><code>int random_w(int *arr, int weights[], int size)
  {
      int selected, i;
      int totalWeight;
      double ratio;
      static long int total;
      static long int *eachTotal = NULL;
      static int *local_arr = NULL;
      static double *weight = NULL;
  
      if (arr != NULL) 
          {
              free(eachTotal);
              free(weight);
              eachTotal = (long int*) calloc(size, sizeof(long));
              weight = (double*) calloc(size, sizeof(double));
              total = 0;
              totalWeight = 0;
              local_arr = arr;
  
              for (i = 0; i &lt; size; i++) 
              {
                  totalWeight += weights[i];
              }
  
              for (i = 0; i &lt; size; i++)
              {
                  weight[i] = (double)weights[i] / totalWeight;
              }
              srand(time(NULL));
          }
  
      while (1)
      {
          selected = rand() % size;
          ratio = (double)(eachTotal[selected])/(double)(total+1);
          if (ratio &lt; weight[selected])
          {
              total++;
              eachTotal[selected]++;
  
              return local_arr[selected];
          }
      }
  }
  </code></pre>