parallelunranking

Documentation

Overview

Package parallelunranking provides functions to unrank set partitions lexicographicaly

The main function of this package is the function UnrankDicho that generates a set partition in exactly k part in the lexicographic order. Our package provides a formula with 4 levels of optimization and paralellism to avoid precomputation step

Index

• Variables
• func S3v1(n, k int, swap bool, d int) big.Int
• func S3v2(n, k int, swap bool, d int) big.Int
• func S3v3(n, k int, swap bool, d int) big.Int
• func S3v4(n, k int, swap bool, d int) big.Int
• func S3v5(n, k int, swap bool, d int) big.Int
• func Stirling2Columns(n, k int) *types.CoupleColumns
• func UnrankDicho(n, k int, rank big.Int, whichS3 int) [][]int

Variables

var StirlingColumn0 []big.Int

var StirlingColumn1 []big.Int

var TimePreviousColumn []int64

var TimePreviousColumnWithK []int64

var TimeTotal int64

var WaitingTime int64

Functions

func S3v1

func S3v1(n, k int, swap bool, d int) big.Int

Direct implementation of the s3 formula (read the readme section Related propositon 7 for more details) n - number of elements in the set k - number of blocks desired swap - flag d - last element of the unranked prefix u - length of the prefix

func S3v2

func S3v2(n, k int, swap bool, d int) big.Int

    Implementation of the s3 formula (read the readme section Related proposition 7 for more details)
	taking in consideration the symmetry of the binomials coefficients to improve the
	computation time of the formula.
	n - number of elements in the set
	k - number of blocks desired
	swap - flag
	d - last element of the unranked prefix
	u - length of the prefix

func S3v3

func S3v3(n, k int, swap bool, d int) big.Int

    Direct implementation of the s3 formula (read the readme section Related proposition 9 for more details)
	n - number of elements in the set
	k - number of blocks desired
	swap - flag
	d - last element of the unranked prefix
	u - length of the prefix

func S3v4

func S3v4(n, k int, swap bool, d int) big.Int

    Direct implementation of the s3 formula (read the readme section Related proposition 9 for more details)
	taking in acount the symmetry of the binomial coefficients to improve computation time.
	n - number of elements in the set
	k - number of blocks desired
	swap - flag
	d - last element of the unranked prefix
	u - length of the prefix

func S3v5

func S3v5(n, k int, swap bool, d int) big.Int

    Take the best of s3v4 and s3v2
	n - number of elements in the set
	k - number of blocks desired
	swap - flag
	d - last element of the unranked prefix

func Stirling2Columns

func Stirling2Columns(n, k int) *types.CoupleColumns

Return the k and the k-1th stirling triangle collumn until the line n.

func UnrankDicho

func UnrankDicho(n, k int, rank big.Int, whichS3 int) [][]int

Unrank set partition lexicographicaly.

This function is the main function of the package and takes 4 arguments as parameters : - n : int, the cardinal of the set to be partitioned. - k : int, the number of desired blocks in the result. - rank : big.Int, the rank of the desired set partition in the lexicographical order. - whichS3: [|0,4|], the desired version of S3 formula to use (4 is the fastest, 0 is the slowest).

For the time complexity, read the README section Related, theorem 12 of the article Example usage:

result := parallelunranking.UnrankDicho(5, 3, *big.NewInt(10), 4)
fmt.Println(result) // Output: [[1 2 3] [4] [5]]