JuliaMath / JuliaMath/Combinatorics.jl

with_replacement_permutations

Open
#118 0 comments 3 reactions 0 assignees View on GitHub
Dominant language
Julia
Stars
230
Forks
62
PR merge metrics
No merged PRs in 30d

Description

I believe it would be useful to add a method to generate permutations with repetitions, so that, for example

julia> collect(with_replacement_permutations(1:2, 2))
4-element Vector{Vector{Int64}}:
[1, 1]
[1, 2]
[2, 1]
[2, 2]

A possible implementation could be the following
````
struct WithReplacementPermutations{T}
a::T
t::Int
end

Base.eltype(::Type{WithReplacementPermutations{T}}) where {T} = Vector{eltype(T)}

Base.length(p::WithReplacementPermutations) = length(p.a)^p.t

"""
with_replacement_permutations(a, t)

Generate all permutations with replacement of size `t` from an array `a`.
"""
with_replacement_permutations(elements::T, len::Integer) where {T} =
WithReplacementPermutations{T}(unique(elements), len)

function Base.iterate(p::WithReplacementPermutations, s = ones(Int, p.t))
(!isempty(s) && s[end] > length(p.a) || (isempty(s) && p.t > 0)) && return
nextpermutationwithreplacement(p.a, p.t, s)
end

function nextpermutationwithreplacement(a, t, state)
cur = a[state]
n = length(state)
state[1] += 1
local i = 1
while i < n && state[i] > length(a)
state[i] = 1
state[i+1] += 1
i += 1
end
return cur, state
end
````

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.