Changes between Initial Version and Version 2 of Ticket #29262


Ignore:
Timestamp:
02/29/20 16:03:58 (16 months ago)
Author:
gh-agenitrini
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #29262

    • Property Authors changed from to Antoine Genitrini
    • Property Component changed from PLEASE CHANGE to combinatorics
    • Property Branch changed from to u/gh-agenitrini/combination_unranking_new_algorithm
    • Property Keywords combination unranking added
    • Property Commit changed from to 268f41a1791a63ab7528a7af0f05eafe1d4b1fab
    • Property Type changed from PLEASE CHANGE to enhancement
  • Ticket #29262 – Description

    initial v2  
     1I propose to implement a new algorithm for the unranking of combinations in the lexicographic order, cf. sage.combinat.combination algorithm from_rank.
     2The actual implementation is related to McCaffrey's blog.
     3In a recent paper I have written, cf. https://hal.archives-ouvertes.fr/hal-02462764v1
     4I 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.
     5
     6If possible I would like to commit this new implementation. My function has the same signature from the previous one.
     7
     8Regards.
     9Antoine
     10
     11
     12Example :
     13Actual implementation (on my laptop : core i7 32GiB Ubuntu Linux)
     14{{{
     15sage: n = 100
     16sage: k = 50
     17sage: set_random_seed(12345678987654321)
     18sage: r = randint(0, binomial(n,k)-1)
     19sage: %time A = combination.from_rank(r,n,k)
     20
     21CPU times: user 1.55 ms, sys: 0 ns, total: 1.55 ms
     22Wall time: 1.06 ms
     23
     24## With my algorithm
     25## (in the commit the function replace from_rank(.,.,.))
     26
     27sage: %time B = unrank_combi_direct(r, n, k)   
     28
     29CPU times: user 297 µs, sys: 53 µs, total: 350 µs
     30Wall time: 296 µs
     31
     32## Finally
     33
     34sage: A==B
     35
     36True
     37
     38
     39## A second example with greater values
     40
     41sage: n = 10000
     42sage: k = 5000
     43sage: set_random_seed(12345678987654321)
     44sage: r = randint(0, binomial(n,k)-1)
     45sage: %time A = combination.from_rank(r,n,k)
     46
     47CPU times: user 2.9 s, sys: 9.69 ms, total: 2.91 s
     48Wall time: 2.85 s
     49
     50## With my algorithm  (in the git branch I obviously reused the function name from_rank)
     51
     52sage: %time B = unrank_combi_direct(r, n, k)
     53
     54CPU times: user 22.4 ms, sys: 4.45 ms, total: 26.9 ms
     55Wall time: 21 ms
     56
     57## Finally
     58
     59sage: A==B
     60
     61True
     62}}}