Skip to content

Instantly share code, notes, and snippets.

@raidzero
Created October 21, 2014 19:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save raidzero/ee12455178490d94a473 to your computer and use it in GitHub Desktop.
Save raidzero/ee12455178490d94a473 to your computer and use it in GitHub Desktop.
Split X into N uniformly-distributed pieces (C)
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
int* split(int n, int numPieces);
int randInt(int min, int max);
int sumList(int* list, int size);
void printList(int* list, int size);
void seedrand();
int main(int argc, char* argv[]) {
int n = atoi(argv[1]);
int numPieces = atoi(argv[2]);
int* list = split(n, numPieces);
int sum = sumList(list, numPieces);
printf("sum: %d\n", sum);
printList(list, numPieces);
free(list);
return 0;
}
int* split(int n, int numPieces) {
seedrand();
int* rtn = (int*) malloc(numPieces * sizeof(int));
int mid = n / numPieces;
int delta = 0;
for (int i = 0; i < numPieces; i++) {
if (i % 2 == 0) {
delta = randInt(0, mid);
} else {
delta = -delta;
}
if (numPieces % 2 != 0 && i == numPieces - 1) {
delta = 0;
}
rtn[i] = mid + delta;
}
int sum = sumList(rtn, numPieces);
int diff;
if (sum > n) {
diff = n - sum;
} else {
diff = sum - n;
}
if (diff != 0) {
for (int i = 0; i < abs(diff); i++) {
int index = randInt(0, numPieces - 1);
if (diff > 0) {
rtn[i] -= 1;
} else {
rtn[i] += 1;
}
}
}
return rtn;
}
int randInt(int min, int max) {
return rand() / (RAND_MAX / (min - max + 1) + 1);
}
int sumList(int* list, int size) {
int total = 0;
for (int i = 0; i < size; i++) {
total += list[i];
}
return total;
}
void printList(int* list, int size) {
printf("[ ");
for (int i = 0; i < size; i++) {
printf("%d", list[i]);
if (i != size - 1) {
printf(", ");
}
}
printf(" ]\n");
}
void seedrand() {
struct timeval tv;
struct timezone tz;
struct tm *tm;
gettimeofday (&tv, &tz);
tm = localtime (&tv.tv_sec);
srand (tv.tv_usec);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment