Opened 14 months ago
Closed 13 months 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 14 months ago by
comment:2 Changed 14 months 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 13 months 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 13 months ago by
- Status changed from needs_review to positive_review
comment:5 Changed 13 months ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
I have not pushed anything yet.