Skip to content

Instantly share code, notes, and snippets.

@fulldecent
Created November 3, 2015 22:13
Show Gist options
  • Select an option

  • Save fulldecent/db203c35417381827014 to your computer and use it in GitHub Desktop.

Select an option

Save fulldecent/db203c35417381827014 to your computer and use it in GitHub Desktop.
// See https://math.stackexchange.com/questions/835031/how-many-ways-to-pick-x-balls
double choose_n_balls(int n, int num_types, int *count_per_type)
{
int total_count = 0;
for (int i = 0; i < num_types; i++) {
total_count += count_per_type[i];
}
if (n > total_count)
return 0;
if (num_types == 1)
return 1;
double retval = 0;
for (int i = 0; i <= count_per_type[0] && i <= n; i++) {
int new_n = n - i;
int new_num_types = num_types - 1;
int new_count_per_type[100] = {0};
memcpy(new_count_per_type, &(count_per_type[1]), sizeof(count_per_type[0]) * 99);
retval += choose_n_balls(new_n, new_num_types, new_count_per_type);
}
return retval;
}
@fulldecent

Copy link
Copy Markdown
Author

There is a hard-coded 100 in there. Watch out.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment