intpart.c File Reference

Partitions of an integer into a given number of summands. More...

#include "intpart.h"
#include "misc.h"
#include "u64u64map.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>

Functions
static uint64_t	numIntPart_r (int32_t n, int32_t k)
	Called by numIntPart. More...
uint64_t	numIntPart (int32_t n, int32_t k)
	Number of ways to partition a positive integer n into k parts. More...
int	traverseIntPartitions (int n, int k, int(*visit)(int kk, int a[kk], void *data), void *data)
	Partition a positive integer n into a sum of k positive integers. More...
void	numIntPart_free (void)
	Free static variable.

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

Detailed Description

Partitions of an integer into a given number of summands.

Copyright

Copyright (c) 2020, 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

numIntPart()

uint64_t numIntPart	(	int32_t	n,
		int32_t	k
	)

Number of ways to partition a positive integer n into k parts.

The public-facing function just locks the map and calls the static recursive function, numIntPart_r.

numIntPart_r()

static uint64_t numIntPart_r ( int32_t  n, int32_t  k  )

static

Called by numIntPart.

This assumes that the map is locked and does the real work of calculating the number of ways to partition a positive integer n into k parts.

traverseIntPartitions()

int traverseIntPartitions	(	int	n,
		int	k,
		int(*)(int kk, int a[kk], void *data)	visit,
		void *	data
	)

Partition a positive integer n into a sum of k positive integers.

Algorithm H, p 392 of Knuth, Donald E. 2011. The art of computer programming, volume 4A.