# Is there an idiomatic way to iterate over all binary strings of a given length?

**URL:** <https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487>\
**Category:** New to Julia\
**Created:** [March 3, 2020, 10:11pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487 "2020-03-03T22:11:31Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![lesshaste](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lesshaste/32/12302_2.png) [@lesshaste](https://discourse.julialang.org/u/lesshaste)\
**Post date:** [March 3, 2020, 10:11pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/1 "2020-03-03T22:11:31Z")

</div>

I would like to iterate over all binary strings of length n, for some smallish integer n. Is there an idiomatic Julia way to do that?

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [March 3, 2020, 10:23pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/2 "2020-03-03T22:23:27Z")

</div>

```julia
for i = 0:2^(n+1)-1
       s = bitstring(i)
       println(s[length(s)-n:end])
end

```

There might be a nicer way to get the last `n` characters of a string, but this was quick and dirty 🙂

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 3, 2020, 10:48pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/3 "2020-03-03T22:48:02Z")

</div>

> [@anon94023334](#):
>
> ```julia
> println("$(s[length(s)-n:end])")
> 
> ```

You don’t need to interpolate here. Just do

```julia
println(s[end-n:end]) 

```

---

<div class="post-metadata">

**Author:** ![mbaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbaz/32/17295_2.png) [@mbaz](https://discourse.julialang.org/u/mbaz)\
**Post date:** [March 3, 2020, 10:58pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/4 "2020-03-03T22:58:44Z")

</div>

Don’t you need to start from 0?

```julia
function bb(n)
    for i = 0:2^n-1
       s = bitstring(i)
       println(s[end-n+1:end])
    end
end

```

and then

```julia
julia> bb(3)
000
001
010
011
100
101
110
111

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 4, 2020, 2:41am UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/5 "2020-03-04T02:41:36Z")

</div>

> [@anon94023334](#):
>
> There might be a nicer way to get the last `n` characters of a string, but this was quick and dirty

`last(somestring, n)`

---

<div class="post-metadata">

**Author:** ![lesshaste](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lesshaste/32/12302_2.png) [@lesshaste](https://discourse.julialang.org/u/lesshaste)\
**Post date:** [March 4, 2020, 8:24am UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/6 "2020-03-04T08:24:47Z")

</div>

Thank you for this. I wonder if there is a lighter weight solution if you need to iterate over a large range (say n = 30), quickly.

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [March 4, 2020, 9:29am UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/7 "2020-03-04T09:29:39Z")

</div>

You may try to implement iterator which goes through [Gray code](https://en.wikipedia.org/wiki/Gray_code), I think it’s as fast and lightweight as it can be. There is no dedicated package, but here is snippet from rosetta code: [RosettaCodeData/gray-code.julia at master · acmeism/RosettaCodeData · GitHub](https://github.com/acmeism/RosettaCodeData/blob/master/Task/Gray-code/Julia/gray-code.julia)

---

<div class="post-metadata">

**Author:** ![lesshaste](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lesshaste/32/12302_2.png) [@lesshaste](https://discourse.julialang.org/u/lesshaste)\
**Post date:** [March 4, 2020, 9:32am UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/8 "2020-03-04T09:32:17Z")

</div>

That would iterate over integers not strings, right? Or were you suggesting I write a new version which iterates over strings?

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [March 4, 2020, 9:41am UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/9 "2020-03-04T09:41:26Z")

</div>

Sorry, my comment can be misleading. Regarding your question, it actually depends on what type of object you are working with. If it’s `String` than I do not think that it is possible to do anything faster than solutions shown above (increase some integer with the following conversion to String). If on the other hand it’s possible to use `BitArray` or `Vector{UInt}` than you can write your own implementation of the Gray Code and mutate corresponding vector inplace.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 4, 2020, 12:24pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/10 "2020-03-04T12:24:41Z")

</div>

> [@lesshaste](#):
>
> I wonder if there is a lighter weight solution if you need to iterate over a large range (say n = 30), quickly. […] That would iterate over integers not strings, right? Or were you suggesting I write a new version which iterates over strings?

Why do you need to use strings? What are you trying to do?

It’s never going to be super fast if you use `String`, because you need to allocate a new string on each iteration.

---

<div class="post-metadata">

**Author:** ![lesshaste](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lesshaste/32/12302_2.png) [@lesshaste](https://discourse.julialang.org/u/lesshaste)\
**Post date:** [March 4, 2020, 12:32pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/11 "2020-03-04T12:32:08Z")

</div>

I guess if I update the strings in Gray code order then I only need to change one entry at a time which could be very fast.

I need strings as I am computing various distances between them. For example the Levenshtein distance.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 4, 2020, 1:08pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/12 "2020-03-04T13:08:17Z")

</div>

> [@lesshaste](#):
>
> I guess if I update the strings in Gray code order then I only need to change one entry at a time which could be very fast.

`String` is immutable in Julia, so it can’t be updated in-place. Of course, you could define your own string type, but a `Vector{Bool}` would be a much more natural choice here than a string.

> [@lesshaste](#):
>
> I need strings as I am computing various distances between them. For example the Levenshtein distance.

It would be easy (and probably more efficient) to implement these distance metrics using `Vector{Bool}`.

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [March 4, 2020, 1:56pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/13 "2020-03-04T13:56:27Z")

</div>

As a side note, you still may use package like `StringDistances` with your own type of String, due to the multiple dispatch, for example

```julia
using StringDistances

struct MyString <: AbstractString
    v::Vector{Bool}
end

Base.:ncodeunits(s::MyString) = length(s.v)
Base.:isvalid(s::MyString, i::Int) = true
Base.:iterate(s::MyString, i::Int) = iterate(s.v, i)

s1 = MyString([true, true, false])
s2 = MyString([false, false, false])
evaluate(Levenshtein(), s1, s2) # 2

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 4, 2020, 2:11pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/14 "2020-03-04T14:11:10Z")

</div>

> [@Skoffer](#):
>
> `Base.:isvalid(s::MyString, i::Int) = true`

Is this right? I’m not familiar with this functionality, but according to the docs:

> If `isvalid(s, i)` is true then `s[i]` will return the character whose encoding starts at that index.

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [March 4, 2020, 2:21pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/15 "2020-03-04T14:21:00Z")

</div>

It depends on what we should consider character in this case. If character is `Bool`, than this definition is correct. If character is group of 8 `Bool` values, than things will be more complicated of course. I suppose then instead of `Vector{Bool}` one should use `Vector{UInt8}`.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 4, 2020, 2:29pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/16 "2020-03-04T14:29:37Z")

</div>

I don’t get it. Why isn’t it

```julia
Base.isvalid(s::MyString, i::Int) = 1 <= i <= length(s.v)

```

for example?

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [March 4, 2020, 2:34pm UTC](https://discourse.julialang.org/t/is-there-an-idiomatic-way-to-iterate-over-all-binary-strings-of-a-given-length/35487/17 "2020-03-04T14:34:07Z")

</div>

Ah, yes, that’s better of course.  
My definition works, because `length` check basically happens inside `iterate` (and this function is mainly used in `StringDistances` algorithms), but in other cases it will fail.