Deterministic weighted random number generator

By: a guest on Nov 18th, 2010  |  syntax: C  |  size: 2.85 KB  |  hits: 100  |  expires: Never
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <time.h>
4.
5. void print(int arr[], int size) {
6.         int i;
7.         for (i = 0; i < size; i++) {
8.                 printf("%d ", arr[i]);
9.         }
10.         printf("\n");
11.
12.         return;
13. }
14.
15. /* http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle */
16. void shuffle(int arr[], int size_of_arr) {
17.         int i, j, temp;
18.         srand(time(NULL));
19.         for (i = size_of_arr-1; i > 0; --i) {
20.                 j = rand() % (i+1);
21.                 temp = arr[i];
22.                 arr[i] = arr[j];
23.                 arr[j] = temp;
24.         }
25. }
26.
27. int random_c(int* items, int items_weight[], int num_of_items) {
28.         /* Usual variables as array indexes */
29.         int i, j, t;
30.         int counter;
31.         /* Its name tells us everything */
32.         int result;
33.         /* big-array : used for storing the items
34.          * in number of items of its weight      */
35.         static int *big_array = NULL;
36.         /* period : equal to the sum of each items weight
37.          * and when random_c(...) is called for  number of times
38.          * which is equal to the period, the big_array will be
39.          * shuffled again in order to get a new sequence */
40.         static int period;
41.         /* current : is used to indicate current item in
42.          * big_array as a result of random_c(...) */
43.         static int current;
44.         /* sum of each items weight */
45.         static int total_weight;
46.
47.         /* If a new array of items had been given */
48.         if (items != NULL) {
49.                 /* calculate total weight */
50.                 total_weight = 0;
51.                 for (i = 0; i < num_of_items; ++i) {
52.                         total_weight += items_weight[i];
53.                 }
54.                 /* If random_c(...) was called with an array of items before
55.                  * delete the previous big_array and create a new one for
56.                  * the new items */
57.                 if (big_array != NULL) {
58.                         free(big_array);
59.                 }
60.                 big_array = (int*) malloc(total_weight * sizeof(int));
61.
62.                 /* Fıll in the big_array with the given items by using their
63.                  * weight as the number of occurence in big_array */
64.                 t = 0;
65.                 for (j = 0; j < num_of_items; ++j) {
66.                         counter = 0;
67.                         while (counter < items_weight[j]) {
68.                                 big_array[t] = items[j];
69.                                 t++;
70.                                 counter++;
71.                         }
72.                 }
73.                 /* New array has come, so shuffle the big_array */
74.                 shuffle(big_array, total_weight);
75.                 period = total_weight;
76.                 current = 0;
77.         }
78.         result = big_array[current];
79.
80.         if (++current == period) {
81.                 current = 0;
82.                 shuffle(big_array, total_weight);
83.         }
84.         return result;
85. }
86.
87. int main(int argc, char** argv)
88. {
89.         int counter;
90.         int arr[] = {1, 2, 3};
91.         int arr_weight[] = {1, 2, 3};
92.         int karr[] = {1, 3, 5, 7};
93.         int karr_weight[] = {1, 3, 5, 7};
94.
95.         printf("---->  %d\n", random_c(arr, arr_weight, 3));
96.         counter = 0;
97.         while (counter++ < 17) {
98.                 sleep(1); /* I compiled it with gcc */
99.                 printf("---->  %d\n", random_c(NULL, arr_weight, 3));
100.         }
101.         printf("\n");
102.
103.         printf("---->  %d\n", random_c(karr, karr_weight, 4));
104.         counter = 0;
105.         while (counter++ < 31) {
106.                 sleep(1);
107.                 printf("---->  %d\n", random_c(NULL, karr_weight, 4));
108.         }
109.         printf("\n");
110.
111.         return 0;
112. }