comb.c File Reference

Combinations. More...

#include "comb.h"
#include "misc.h"
#include "u64i64map.h"
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <pthread.h>

Data Structures
struct	MCdat

Functions
MCdat *	MCdat_new (int k, int n[k], int(*visit)(int kk, int nn[kk], int *b[kk], void *data), void *data)
void	MCdat_free (MCdat *self)
int	MCvisit (int t, int *a, void *data)
int	traverseMultiComb (int k, int n[k], int(*visit)(int kk, int nn[kk], int *b[kk], void *data), void *data)
	Visit each way of allocating N balls among k boxes, such that there are b[0] balls in the first box, b[1] in the second, and so on up to b[k-1], and where N is the sum of the b[i].
int	traverseComb (int n, int t, int(*visit)(int tt, int *c, void *data), void *data)
long	multinom (int k, int x[k])
	Return N!
static int64_t	binom_r (int32_t n, int32_t x)
int64_t	binom (int32_t n, int32_t x)
	Binomial coefficient.
void	binom_free (void)
	Free the hash map used to store binom values.

Variables
static pthread_mutex_t	map_lock = PTHREAD_MUTEX_INITIALIZER
static U64I64Map *	map =NULL

Detailed Description

Combinations.

Author

Alan R. Rogers

Copyright

Copyright (c) 2019, Alan R. Rogers roger.nosp@m.s@an.nosp@m.thro..nosp@m.utah.nosp@m..edu. This file is released under the Internet Systems Consortium License, which can be found in file "LICENSE".

Function Documentation

multinom()

long multinom	(	int	k,
		int	x[k] )

Return N!

/(prod x[i]!), the number of ways of allocating N = sum(x[i]) balls among k boxes, with x[i] balls in the ith box.

Parameters

[in]	k	The number of boxes.
[in]	x	An array of k positive integers, with x[i] representing the number of balls in box i.

traverseMultiComb()

int traverseMultiComb	(	int	k,
		int	n[k],
		int(*	visit )(int kk, int nn[kk], int *b[kk], void *data),
		void *	data )

Visit each way of allocating N balls among k boxes, such that there are b[0] balls in the first box, b[1] in the second, and so on up to b[k-1], and where N is the sum of the b[i].

For each combination visited, the "visit" function is called.

Parameters

[in]	k	The number of boxes.
[in]	n[k]	The number of balls to be allocated to the k'th box.
[in]	visit	A function to be called for each combination visited. The arguments of this function are kk, the number of boxes; nn, an array whose i'th entry is the number of balls in box i; b, an array of kk arrays. The i'th entry of b is an array of nn[i] non-negative integers, whose j'th entry is the index of the j'th ball in box i. These indices range from 0 to N-1 inclusive, and each of these N index values is present exactly once in the two-dimensional array b. The last argument of the visit function is a void pointer, which will hold the address of the data argument passed to the traverseMultiComb function.
[in,out]	data	If non-NULL, data points to a structure to be manipulated by the visit function.