Created
October 21, 2014 19:02
-
-
Save raidzero/ee12455178490d94a473 to your computer and use it in GitHub Desktop.
Split X into N uniformly-distributed pieces (C)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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