# New implementation for the lexicographic unranking of combinations

Reported by: Owned by: gh-agenitrini major sage-duplicate/invalid/wontfix combinatorics combination unranking Antoine Genitrini Dave Morris N/A

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

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

I have not pushed anything yet.

Last edited 16 months ago by gh-agenitrini (previous) (diff)

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

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 15 months ago by gh-DaveWitteMorris

• 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 15 months ago by gh-DaveWitteMorris

• Status changed from needs_review to positive_review

### comment:5 Changed 15 months ago by chapoton

• Resolution set to duplicate
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.