Adding a function nthcomb() to Combinatorics.jl

General Usage
,
1

I recently had a project that required writing code for generating Nth lexicographic combinations of size k. Combinatorics.jl has nthperm, but not the equivalent for combinations. If there is interest in adding this functionality to the package, I’d like to contribute. I’m relatively new to the Julia community, so before opening a PR, I wanted to post here to assess interest, get some pointers on contributing in Julia, and get some design input. Alternatively, if the best thing to do is just open a PR please let me know.

Naming – I went with argument names closer to “n-choose-k” but realize this doesn’t match the general argument naming convention used in Combinatorics.jl. I’m thinking a = collection, n = # elements in collection, t = # elements in combination, m = the lexicographic index to be consistent with existing functions in this package.

Algorithm – The code performance met my needs, but I know there’s room for optimization here, for example binary search for the next value could be better than a linear search as a start, and knowing my limitations in Julia.

My internal code is copied below.


# return indices for 1:n indexed collection
"""
`nthcomb(n,k,m)`

Compute the `m`th lexicographic combination of size `k` from collection with `n` elements with assumed values `1:n`. equivalent to `collect(combinations(1:n,k))[m]`    
"""
function nthcomb(n::Integer,k::Integer,m::Integer)

    # finds the combinadic of the dual of the index requested and then converts to the actual element indices
    m = binomial(n,k)-m # convert to dual
    if n==k
        return 1:n
    end

    cm = Vector{Integer}(undef,k)
    for kidx in k:-1:1
        cm[k-kidx+1],m = leadingidx(kidx,m)
    end

    return(combinadic2element!(cm,n).+1)

end

"""
`nthcomb(a,k,m)`

Compute the `m`th lexicographic combination of size `k` from collection `a`. equivalent to `collect(combinations(a,k))[m]`
"""
function nthcomb(a::AbstractVector,k::Integer,m::Integer)
    em = nthcomb(length(a),k,m)
    return a[em]
end

# find leading index for `m`th lexicographic combination of size k, helper for nthcomb
function leadingidx(k::Integer,m::Integer)
    # the leading index in the combination is the term n such that nCk < m
    test_n = k-1
    nCk = binomial(test_n,k)
    nCk_old = 0
    
    while nCk <= m
        nCk_old = nCk
        test_n+=1
        nCk = binomial(test_n,k)
    end
    return (test_n-1,m-nCk_old)
end

function combinadic2element!(cm,n)
    cm = (n-1) .- cm
    return cm
end

# test
n = 8
k = 3
[nthcomb(n,k,i) for i in 1:binomial(n,k)] == collect(combinations(1:n,k))
[nthcomb(1:n,k,i) for i in 1:binomial(n,k)] == collect(combinations(1:n,k))
2

You probably don’t want to instantiate vectors as cm = Vector{Integer}(undef,k) because

julia> isabstracttype(Integer)
true

better:

julia> isabstracttype(Int)
false
1 Like
3

Thanks! Got rid of the majority of the allocations.