# Combination unranking new algorithm

Reported by: Owned by: gh-agenitrini major sage-9.1 combinatorics combination unranking Antoine Genitrini Travis Scrimshaw N/A 845c21e 845c21e3e4c1c2890aaa7cc06e8810d39a756ba0

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
```

### comment:1 Changed 17 months ago by gh-agenitrini

• Branch set to u/gh-agenitrini/combination_unranking_new_algorithm

### comment:2 Changed 17 months ago by gh-agenitrini

• Authors set to Antoine Genitrini
• Commit set to 268f41a1791a63ab7528a7af0f05eafe1d4b1fab
• Component changed from PLEASE CHANGE to combinatorics
• Description modified (diff)
• Type changed from PLEASE CHANGE to enhancement

### comment:3 Changed 17 months ago by gh-agenitrini

• Status changed from new to needs_review

### comment:4 Changed 17 months ago by git

• Commit changed from 268f41a1791a63ab7528a7af0f05eafe1d4b1fab to 9a7a3ccaf713ea06371a79f093a35b155f744837

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

 ​9a7a3cc `function from_rank in combinatorics.py modified`

### comment:5 Changed 17 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 17 months ago by git

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

 ​0232cd6 `reference [DGH2020] added in index.rst`

### comment:7 Changed 17 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 17 months ago by git

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

 ​24799fb `test for the possible values of r corrected`

### comment:9 Changed 17 months ago by git

• 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 17 months ago by gh-agenitrini

• Status changed from needs_work to needs_review

### comment:11 Changed 17 months ago by tscrim

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

Thank you. LGTM.

### comment:12 Changed 17 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 17 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 17 months ago by git

• 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 17 months ago by gh-agenitrini

• Status changed from needs_work to needs_review

### comment:16 Changed 17 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 17 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:

 ​b142db6 `Merge branch 'u/gh-agenitrini/combination_unranking_new_algorithm' of git://trac.sagemath.org/sage into public/combinat/new_combination_unranking-29262` ​845c21e `Adding a systematic test against old version.`

### comment:18 Changed 17 months ago by tscrim

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

### comment:19 Changed 17 months ago by gh-agenitrini

The tests are fine to me, thanks.

### comment:20 Changed 17 months ago by tscrim

• Status changed from needs_review to positive_review

### comment:21 Changed 17 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.