#29258 closed enhancement (duplicate)

New implementation for the lexicographic unranking of combinations

Reported by: gh-agenitrini Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: combinatorics Keywords: combination unranking
Cc: Merged in:
Authors: Antoine Genitrini Reviewers: Dave Morris
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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

Change History (5)

comment:1 Changed 14 months ago by gh-agenitrini

I have not pushed anything yet.

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

comment:2 Changed 14 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 13 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 13 months ago by gh-DaveWitteMorris

  • Status changed from needs_review to positive_review

comment:5 Changed 13 months ago by chapoton

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