# Adding a function nthcomb() to Combinatorics.jl

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
end

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

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

``````

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

Thanks! Got rid of the majority of the allocations.