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: |
Description (last modified by )
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
- Branch set to u/gh-agenitrini/combination_unranking_new_algorithm
comment:2 Changed 17 months ago by
- 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