Opened 2 years ago
Closed 2 years ago
#29258 closed enhancement (duplicate)
New implementation for the lexicographic unranking of combinations
Reported by: | gh-agenitrini | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | combinatorics | Keywords: | combination unranking |
Cc: | Merged in: | ||
Authors: | Antoine Genitrini | Reviewers: | Dave Morris |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
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)
--- n = 100 k = 50 set_random_seed(12345678987654321) r = randint(0, binomial(n,k)-1) %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(.,.,.)) %time B = unrank_combi_direct(r, n, k) --- CPU times: user 297 µs, sys: 53 µs, total: 350 µs Wall time: 296 µs ## Finally --- A==B --- True ## A second example with greater values --- n = 10000 k = 5000 set_random_seed(12345678987654321) r = randint(0, binomial(n,k)-1) %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 %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 --- A==B --- True
Change History (5)
comment:1 Changed 2 years ago by
comment:2 Changed 2 years ago by
This ticket can be closed or removed, because it is not associated to any branch.
The adequate ticket for this issue and the associated branch are given in the ticket #29262. Sorry for the trouble.
comment:3 Changed 2 years ago by
- Milestone changed from sage-9.1 to sage-duplicate/invalid/wontfix
- Reviewers set to Dave Morris
- Status changed from new to needs_review
comment:4 Changed 2 years ago by
- Status changed from needs_review to positive_review
comment:5 Changed 2 years ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
I have not pushed anything yet.