Opened 15 months ago
Closed 14 months ago
#29262 closed enhancement (fixed)
Combination unranking new algorithm
Reported by:  ghagenitrini  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  combinatorics  Keywords:  combination unranking 
Cc:  Merged in:  
Authors:  Antoine Genitrini  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  845c21e (Commits, GitHub, GitLab)  Commit:  845c21e3e4c1c2890aaa7cc06e8810d39a756ba0 
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.archivesouvertes.fr/hal02462764v1 I compare this method to other from the literature and a new one I have developed with my coauthors. 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 (21)
comment:1 Changed 15 months ago by
 Branch set to u/ghagenitrini/combination_unranking_new_algorithm
comment:2 Changed 15 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
comment:3 Changed 15 months ago by
 Status changed from new to needs_review
comment:4 Changed 15 months ago by
 Commit changed from 268f41a1791a63ab7528a7af0f05eafe1d4b1fab to 9a7a3ccaf713ea06371a79f093a35b155f744837
comment:5 Changed 15 months ago by
This is quite a nice improvement. So it would be good to add [DGH20]
to the master references file (as [DGH2020]
) and then cite it as [DGH20]_
(or with the changed name [DGH2020]_
). Other than that, a few PEP8 space around operators:
if k < n/2: +if k < n / 2: k = nk +k = n  k while d < k1: +while d < k  1: if n1m==0: +if n  1  m == 0: B = (B * (k1i))//(n1m) +B = (B * (k1i)) // (n1m) D[k1] = n+r+k1B +D[k1] = n + r + k  1  B
and these can be simplified:
D = [0 for i in range(k)] +D = [0]*k d = d + 1 +d += 1 i = i + 1 +i += 1 n = n  1 +n += 1 r = r  B +r = B m = m + 1 +m += 1 j = j + 1 +j += 1
Also would it be possible to keep the same variable names as before? While I doubt anyone is explicitly calling it with n=foo
, it is still good in terms of being fully backwards compatible. Plus I feel it would be better to define n0 = n
instead of the other way around.
comment:6 Changed 15 months ago by
 Commit changed from 9a7a3ccaf713ea06371a79f093a35b155f744837 to 0232cd602af8f3ad27bd4dfadbf5d04d37933d43
Branch pushed to git repo; I updated commit sha1. New commits:
0232cd6  reference [DGH2020] added in index.rst

comment:7 Changed 15 months ago by
 Status changed from needs_review to needs_work
Looks like you have some corner case issues appearing in src/sage/combinat/subset.py
.
comment:8 Changed 15 months ago by
 Commit changed from 0232cd602af8f3ad27bd4dfadbf5d04d37933d43 to 24799fbb4c496df7ec5ca35782a984dae11972e2
Branch pushed to git repo; I updated commit sha1. New commits:
24799fb  test for the possible values of r corrected

comment:9 Changed 15 months ago by
 Commit changed from 24799fbb4c496df7ec5ca35782a984dae11972e2 to e83efe8d55a54e90377ef25449748ffa91aeb3cd
Branch pushed to git repo; I updated commit sha1. New commits:
e83efe8  Case n=0 now taken into account

comment:10 Changed 14 months ago by
 Status changed from needs_work to needs_review
comment:11 Changed 14 months ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
Thank you. LGTM.
comment:12 Changed 14 months ago by
 Status changed from positive_review to needs_work
sage t long warnlong 35.8 src/sage/rings/polynomial/pbori.pyx # 3 doctests failed sage t long warnlong 35.8 src/sage/matrix/matrix_mpolynomial_dense.pyx # 4 doctests failed
comment:13 Changed 14 months ago by
So here is the problem:
sage: from sage.combinat.combination import from_rank sage: from_rank(0, 2, 1) (1,) sage: from_rank(1, 2, 1) (2,)
instead this should be (0,)
and (1,)
. I haven't traced through the algorithm, but from testing, this seems to be just some special corner case (if indeed there is no bug in the implementation). It works on larger values of n
and k
.
comment:14 Changed 14 months ago by
 Commit changed from e83efe8d55a54e90377ef25449748ffa91aeb3cd to 110e94f0ebacf614a5d8083650e136daed6b5efe
Branch pushed to git repo; I updated commit sha1. New commits:
110e94f  corner case n == 2 and k == 1 corrected with a direct answer when k == 1

comment:15 Changed 14 months ago by
 Status changed from needs_work to needs_review
comment:16 Changed 14 months ago by
Thank you. Green patchbot now. (Interestingly, there was a green patchbot on the previous version, so I was disregarding the other failing tests.) However, I am going to add a more systematic test (which is how I caught the corner case) on a push tomorrow morning. Should be trivial to review.
comment:17 Changed 14 months ago by
 Branch changed from u/ghagenitrini/combination_unranking_new_algorithm to public/combinat/new_combination_unranking29262
 Commit changed from 110e94f0ebacf614a5d8083650e136daed6b5efe to 845c21e3e4c1c2890aaa7cc06e8810d39a756ba0
comment:18 Changed 14 months ago by
Green bot. If you agree with my changes, then please set it back to a positive review.
comment:19 Changed 14 months ago by
The tests are fine to me, thanks.
comment:20 Changed 14 months ago by
 Status changed from needs_review to positive_review
comment:21 Changed 14 months ago by
 Branch changed from public/combinat/new_combination_unranking29262 to 845c21e3e4c1c2890aaa7cc06e8810d39a756ba0
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
function from_rank in combinatorics.py modified