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
Constants ¶
This section is empty.
Variables ¶
var StirlingColumn0 []big.Int
var StirlingColumn1 []big.Int
var TimePreviousColumn []int64
var TimePreviousColumnWithK []int64
var TimeTotal int64
var WaitingTime int64
Functions ¶
func S3v1 ¶ added in v1.1.0
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 ¶ added in v1.1.0
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 ¶ added in v1.1.0
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 ¶ added in v1.1.0
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 ¶ added in v1.1.0
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 ¶
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]]
Types ¶
This section is empty.
Source Files