Opened 17 months ago

Last modified 17 months ago

#29262 closed enhancement

Combination unranking new algorithm — at Version 2

Reported by: gh-agenitrini Owned by:
Priority: major Milestone: sage-9.1
Component: combinatorics Keywords: combination unranking
Cc: Merged in:
Authors: Antoine Genitrini Reviewers:
Report Upstream: N/A Work issues:
Branch: u/gh-agenitrini/combination_unranking_new_algorithm (Commits, GitHub, GitLab) Commit: 268f41a1791a63ab7528a7af0f05eafe1d4b1fab
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-agenitrini)

I propose to implement a new algorithm for the unranking of combinations in the lexicographic order, cf. sage.combinat.combination algorithm from_rank. The actual implementation is related to McCaffrey?'s blog. In a recent paper I have written, cf. https://hal.archives-ouvertes.fr/hal-02462764v1 I compare this method to other from the literature and a new one I have developed with my co-authors. The paper is actually under review.

If possible I would like to commit this new implementation. My function has the same signature from the previous one.

Regards. Antoine

Example : Actual implementation (on my laptop : core i7 32GiB Ubuntu Linux)

sage: n = 100
sage: k = 50
sage: set_random_seed(12345678987654321)
sage: r = randint(0, binomial(n,k)-1)
sage: %time A = combination.from_rank(r,n,k)

CPU times: user 1.55 ms, sys: 0 ns, total: 1.55 ms
Wall time: 1.06 ms

## With my algorithm
## (in the commit the function replace from_rank(.,.,.))

sage: %time B = unrank_combi_direct(r, n, k)   

CPU times: user 297 µs, sys: 53 µs, total: 350 µs
Wall time: 296 µs

## Finally

sage: A==B

True


## A second example with greater values

sage: n = 10000
sage: k = 5000
sage: set_random_seed(12345678987654321)
sage: r = randint(0, binomial(n,k)-1)
sage: %time A = combination.from_rank(r,n,k)

CPU times: user 2.9 s, sys: 9.69 ms, total: 2.91 s
Wall time: 2.85 s

## With my algorithm  (in the git branch I obviously reused the function name from_rank)

sage: %time B = unrank_combi_direct(r, n, k)

CPU times: user 22.4 ms, sys: 4.45 ms, total: 26.9 ms
Wall time: 21 ms

## Finally

sage: A==B

True

Change History (2)

comment:1 Changed 17 months ago by gh-agenitrini

  • Branch set to u/gh-agenitrini/combination_unranking_new_algorithm

comment:2 Changed 17 months ago by gh-agenitrini

  • Authors set to Antoine Genitrini
  • Commit set to 268f41a1791a63ab7528a7af0f05eafe1d4b1fab
  • Component changed from PLEASE CHANGE to combinatorics
  • Description modified (diff)
  • Keywords combination unranking added
  • Type changed from PLEASE CHANGE to enhancement
Note: See TracTickets for help on using tickets.