New implementation for the lexicographic unranking of combinations

[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)

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

Component: combinatorics

Keywords: combination unranking

Author: Antoine Genitrini

Reviewer: Dave Morris

Issue created by migration from https://trac.sagemath.org/ticket/29258

[agenitrini]

comment:1

I have not pushed anything yet.

[agenitrini]

comment:2

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.

[DaveWitteMorris]

Reviewer: Dave Morris