Generate all words of a given size from a fixed alphabet

General Usage
1

Hello,

Say I have an alphabet of n symbols, and I want to generate all words of length k that can exist in that alphabet. What is the concise way to do that in Julia? I am expecting a list of n^k words. Writing k nested for loops looks a bit dull. This sounds something that should be a one-liner with Combinatorics.jl, but I can’t find a decent doc for it.

Thanks in advance.

1 Like
2

Here’s a simple way. No need for Combinatorics even, just plain Iterators.

julia> alphabet = 'a':'d';

julia> k = 2;

julia> join.(collect(Iterators.product(ntuple(_ -> alphabet, k)...))[:])
16-element Array{String,1}:
 "aa"
 "ba"
 "ca"
 "da"
 "ab"
 "bb"
 "cb"
 "db"
 "ac"
 "bc"
 "cc"
 "dc"
 "ad"
 "bd"
 "cd"
 "dd"
6 Likes
3

This is a bit more verbose, but gives you a lazy iterator (similar to Combinatorics.jl types) for this problem.

struct WithReplacementOrderedCombinations{T}
    itr::T
    count::Int64
    itrsize::Int64
    function WithReplacementOrderedCombinations(itr::T,count::Int) where T
        new{T}(itr,Int64(count),length(itr))
    end
end

function Base.iterate(c::WithReplacementOrderedCombinations{T},state::Int64=0) where T
    if state>=length(c)
        return nothing
    end
    indices=digits(state,base=c.itrsize,pad=c.count)
    T([c.itr[i] for i in (indices .+1)]),state+1
end

function Base.length(c::WithReplacementOrderedCombinations)
    length(c.itr) ^ c.count
end

julia> alphabet = "abcd";

julia> k = 2;

julia> collect(WithReplacementOrderedCombinations(alphabet,k))
9-element Array{Any,1}:
 "aa"
 "ba"
 "ca"
 "ab"
 "bb"
 "cb"
 "ac"
 "bc"
 "cc"
3 Likes
4

Iterators.product is actually already lazy. I collected it above since it sounded like that’s what OP wanted, but we can just as well iterate over it lazily:

alphabet = 'a':'d' # or "abcd"
k = 2

itr = Iterators.product(ntuple(_ -> alphabet, k)...)

for word in Base.Generator(join, itr)
    println(word)
    word == "bb" && break
end

Output:

aa
ba
ca
da
ab
bb
5 Likes
6

Thats neat! I didn’t know that.

7

Thanks!