#29262 closed enhancement (fixed)

Combination unranking new algorithm

Reported by: gh-agenitrini Owned by:
Priority: major Milestone: sage-9.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:

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 (21)

comment:1 Changed 15 months ago by gh-agenitrini

  • Branch set to u/gh-agenitrini/combination_unranking_new_algorithm

comment:2 Changed 15 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

comment:3 Changed 15 months ago by gh-agenitrini

  • Status changed from new to needs_review

comment:4 Changed 15 months ago by git

  • Commit changed from 268f41a1791a63ab7528a7af0f05eafe1d4b1fab to 9a7a3ccaf713ea06371a79f093a35b155f744837

Branch pushed to git repo; I updated commit sha1. New commits:

9a7a3ccfunction from_rank in combinatorics.py modified

comment:5 Changed 15 months ago by tscrim

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 = n-k
+k = n - k

-while d < k-1:
+while d < k - 1:

-if n-1-m==0:
+if n - 1 - m == 0:

-B = (B * (k-1-i))//(n-1-m)
+B = (B * (k-1-i)) // (n-1-m)

-D[k-1] = n+r+k-1-B
+D[k-1] = 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 git

  • Commit changed from 9a7a3ccaf713ea06371a79f093a35b155f744837 to 0232cd602af8f3ad27bd4dfadbf5d04d37933d43

Branch pushed to git repo; I updated commit sha1. New commits:

0232cd6reference [DGH2020] added in index.rst

comment:7 Changed 15 months ago by tscrim

  • 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 git

  • Commit changed from 0232cd602af8f3ad27bd4dfadbf5d04d37933d43 to 24799fbb4c496df7ec5ca35782a984dae11972e2

Branch pushed to git repo; I updated commit sha1. New commits:

24799fbtest for the possible values of r corrected

comment:9 Changed 15 months ago by git

  • Commit changed from 24799fbb4c496df7ec5ca35782a984dae11972e2 to e83efe8d55a54e90377ef25449748ffa91aeb3cd

Branch pushed to git repo; I updated commit sha1. New commits:

e83efe8Case n=0 now taken into account

comment:10 Changed 14 months ago by gh-agenitrini

  • Status changed from needs_work to needs_review

comment:11 Changed 14 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Thank you. LGTM.

comment:12 Changed 14 months ago by vbraun

  • Status changed from positive_review to needs_work
sage -t --long --warn-long 35.8 src/sage/rings/polynomial/pbori.pyx  # 3 doctests failed
sage -t --long --warn-long 35.8 src/sage/matrix/matrix_mpolynomial_dense.pyx  # 4 doctests failed

comment:13 Changed 14 months ago by tscrim

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 git

  • Commit changed from e83efe8d55a54e90377ef25449748ffa91aeb3cd to 110e94f0ebacf614a5d8083650e136daed6b5efe

Branch pushed to git repo; I updated commit sha1. New commits:

110e94fcorner case n == 2 and k == 1 corrected with a direct answer when k == 1

comment:15 Changed 14 months ago by gh-agenitrini

  • Status changed from needs_work to needs_review

comment:16 Changed 14 months ago by tscrim

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 tscrim

  • Branch changed from u/gh-agenitrini/combination_unranking_new_algorithm to public/combinat/new_combination_unranking-29262
  • Commit changed from 110e94f0ebacf614a5d8083650e136daed6b5efe to 845c21e3e4c1c2890aaa7cc06e8810d39a756ba0

Here is my trivial change and additional doctest.


New commits:

b142db6Merge branch 'u/gh-agenitrini/combination_unranking_new_algorithm' of git://trac.sagemath.org/sage into public/combinat/new_combination_unranking-29262
845c21eAdding a systematic test against old version.

comment:18 Changed 14 months ago by tscrim

Green bot. If you agree with my changes, then please set it back to a positive review.

comment:19 Changed 14 months ago by gh-agenitrini

The tests are fine to me, thanks.

comment:20 Changed 14 months ago by tscrim

  • Status changed from needs_review to positive_review

comment:21 Changed 14 months ago by vbraun

  • Branch changed from public/combinat/new_combination_unranking-29262 to 845c21e3e4c1c2890aaa7cc06e8810d39a756ba0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.