Creating an Iterable of Dicts

General Usage Performance
,
1

Hi. I’m interested in learning more about creating Iterables to save space. In particular, right now I want to create an Iterable that runs through the rows of a truth table. The following code generates an array that (almost) contains what I want, however an array will take up exponental space, when what I actually want is to iterate over the rows implemented as Dicts:

vars = Set(["a","b","c"])
map(t->Dict(zip(vars,t)),Base.product([false:true for k in vars]...))

The idea is that each Dict-row represents a unique assignment of true/false values to the variable names contained in vars. I’ve only just discovered Base.product(), and it serves its purpose here of generating the assignments, however it only generates them as Tuples, so I still have to map them onto Dicts, which then essentially collects the rows, rather than leaving them as an abstract Iterable. Ideally, I’d also like to specify the order of iteration in the classic binary counting sequence. Can anyone help?

Thanks! :smiley:

1 Like
2

Each Dict must collect the row upon instantiation regardless, but you can make the outer loop lazy by replacing map with Iterators.map.

There was also help thread on the Humans of Julia Discord similar to this a while back, perhaps these can serve as inspiration (I do not take credit for these)!

#1
hcat(collect(vcat.(Iterators.product(Iterators.repeated([true, false], 10)...)...))...)

#2
d=BitArray.(digits.(0:1023, base=2, pad=10))
[d[i][j] for i in 1:1024, j in 1:10]

#3
BitMatrix((i>>j)&1 > 0 for i in 0:1023, j in 0:9)

#4
function tt(length::Integer)
  function bitmask(x::Integer)
    result = BitArray(undef, length)
    result.chunks[1] = x%UInt64
    result
  end
  [bitmask(j) for j in  in 0:2^length-1]
end

#5
using Combinatorics
truthtable(x) = [1:x .in [c] for c in combinations(x)]

#6
function with_sixteen()
    m=BitMatrix(undef,16,1024)
    m.=0
    for x in 0:1023
        chunk_number=((x*16)÷64)+1 #yay one based indexing
        offset=(x*16)%64
        m.chunks[chunk_number]|=x<<offset
    end
    m[1:10,:]
end

#7
function shock_horror()
    m=BitMatrix(undef,1024,10)
    m.chunks[145:160].=0x5555555555555555
    m.chunks[129:144].=0x3333333333333333
    m.chunks[113:128].=0x0f0f0f0f0f0f0f0f
    m.chunks[97:112] .=0x00ff00ff00ff00ff
    m.chunks[81:96]  .=0x0000ffff0000ffff
    m.chunks[65:80]  .=0x00000000ffffffff
    for chun in 1:64
        on_range=2^((64-chun)÷16)
        repeat_range = 2*on_range
        m.chunks[chun] = ((chun%repeat_range)<on_range) ? 0xffffffffffffffff : 0
    end
    m
end

#8
using Combinatorics
n = 2
multiset_permutations([true, false], [n, n], n)

#9
Iterators.product(repeat([[true, false]], n)...)

#10
Iterators.product(Iterators.repeated([⊤, ⊥], n)...)

#11
digits.(0:2^n-1, base=2, pad=n)

#12
Iterators.map(i -> map((!) ∘ Bool, digits(i; base = 2, pad = n)), 0:(2 ^ big(n) - 1))
3

Many thanks - I shall digest this and get back to you!

4

Something like this?

((v=>vt for (v,vt) in zip(vars,t)) for t in Base.product(((false,true) for k in vars)...))

Not collect, just an iterable of iterables.

5

Oh wow. I’m always amazed at how much I learn by asking questions on this forum. Thanks so much to both of you. In retrospect, it seems a little silly of me, but I had never realised that it is not the comprehension that actualises a vector, but the square brackets around it. So in principle, Tuples are lazy, whereas Vectors are … industrious, correct?

What I’m still unclear about is exactly whereabouts in this last solution the Dict gets created. When I pick the command to pieces, I just get a Tuple of Pairs, but somewhere in your command this gets turned into a Dict.

6

Oh no, sorry: I got mixed up. This last solution doesn’t produce a Dict at all - just the Tuples. I shall investigate further … :grinning:

7

Et voila:

vars = Set(["a","b","c"])
a = Iterators.map(
    Dict,
    (zip(vars,reverse(tvalue)) for tvalue in Base.product(((false,true) for _ in vars)...))
)
for i in a
    println(i)
end

Output:

Dict{String, Bool}("c" => 0, "b" => 0, "a" => 0)
Dict{String, Bool}("c" => 0, "b" => 0, "a" => 1)
Dict{String, Bool}("c" => 0, "b" => 1, "a" => 0)
Dict{String, Bool}("c" => 0, "b" => 1, "a" => 1)
Dict{String, Bool}("c" => 1, "b" => 0, "a" => 0)
Dict{String, Bool}("c" => 1, "b" => 0, "a" => 1)
Dict{String, Bool}("c" => 1, "b" => 1, "a" => 0)
Dict{String, Bool}("c" => 1, "b" => 1, "a" => 1)

Many thanks! :smiley:

8

Ok, but this is equivalent to your first solution no? I thought that you didn’t want to instantiate the dictionaries, just iterate over their pairs.

9

I don’t think so, no. This line is still uninstantiated:

a = Iterators.map(
    Dict,
    (zip(vars,reverse(tvalue)) for tvalue in Base.product(((false,true) for _ in vars)...))
)
Base.Generator{Base.Generator{Base.Iterators.ProductIterator{Tuple{Tuple{Bool, Bool}, Tuple{Bool, Bool}, Tuple{Bool, Bool}}}, var"#3#5"}, Type{Dict}}(Dict, Base.Generator{Base.Iterators.ProductIterator{Tuple{Tuple{Bool, Bool}, Tuple{Bool, Bool}, Tuple{Bool, Bool}}}, var"#3#5"}(var"#3#5"(), Base.Iterators.ProductIterator{Tuple{Tuple{Bool, Bool}, Tuple{Bool, Bool}, Tuple{Bool, Bool}}}(((false, true), (false, true), (false, true)))))
10

Yep, sorry, I meant replacing map with Iterators.map as in the first response to your query.

11

:+1: :grinning:

12 
itr=( Dict(vars.=>(a,b,c)) for a in [false,true], b in [false,true], c in [false,true])


itr=( Dict(vars.=>t) for t in  Base.product([false,true],[false,true],[false,true]))

or more generally

julia> itr=( Dict(vars.=>t) for t in  Base.product(repeat([[false,true]],length(vars))...))
Base.Generator{Base.Iterators.ProductIterator{Tuple{Vector{Bool}, Vector{Bool}, Vector{Bool}}}, var"#35#36"}(var"#35#36"(), Base.Iterators.ProductIterator{Tuple{Vector{Bool}, Vector{Bool}, Vector{Bool}}}((Bool[0, 1], Bool[0, 1], Bool[0, 1])))



julia> for i in itr
           println(i)
       end
Dict{String, Bool}("c" => 0, "b" => 0, "a" => 0)
Dict{String, Bool}("c" => 1, "b" => 0, "a" => 0)
Dict{String, Bool}("c" => 0, "b" => 1, "a" => 0)
Dict{String, Bool}("c" => 1, "b" => 1, "a" => 0)
Dict{String, Bool}("c" => 0, "b" => 0, "a" => 1)
Dict{String, Bool}("c" => 1, "b" => 0, "a" => 1)
Dict{String, Bool}("c" => 0, "b" => 1, "a" => 1)
Dict{String, Bool}("c" => 1, "b" => 1, "a" => 1)
13

Oh, nice one, @rocco_sprmnt21. Thanks very much! :smiley:

14

Thank you. This code is intended as part of a course on Syntax and Logic that I am writing, so I wanted the code to be as comprehensible as possible. So in the light of the latest solution, this is now my favoured solution:

julia> Model = Dict{String,Bool}
Dict{String, Bool}

julia> vars = Set(["a","b","c"])
Set{String} with 3 elements:
  "c"
  "b"
  "a"

julia> (Model(vars.=>reverse(t_row)) for t_row in
    Base.product(((false,true) for _ in vars)...)
)
Base.Generator{Base.Iterators.ProductIterator{Tuple{Tuple{Bool, Bool}, Tuple{Bool, Bool}, Tuple{Bool, Bool}}}, var"#7#9"}(var"#7#9"(), Base.Iterators.ProductIterator{Tuple{Tuple{Bool, Bool}, Tuple{Bool, Bool}, Tuple{Bool, Bool}}}(((false, true), (false, true), (false, true))))

julia> for i in ans
    println(i)
end
Dict{String, Bool}("c" => 0, "b" => 0, "a" => 0)
Dict{String, Bool}("c" => 0, "b" => 0, "a" => 1)
Dict{String, Bool}("c" => 0, "b" => 1, "a" => 0)
Dict{String, Bool}("c" => 0, "b" => 1, "a" => 1)
Dict{String, Bool}("c" => 1, "b" => 0, "a" => 0)
Dict{String, Bool}("c" => 1, "b" => 0, "a" => 1)
Dict{String, Bool}("c" => 1, "b" => 1, "a" => 0)
Dict{String, Bool}("c" => 1, "b" => 1, "a" => 1)
15 
Just out of curiosity. What is the purpose of the reverse function?
16

Oh, right, yes. That was really just a question of my own taste. As I say, I intend this code for use with students, so I want everything they do and all the results of their programming to be as self-evident as possible. And it just feels to me that it’s easier for them to understand if the truth-table is in the usual binary counting order, where the right-hand bits change quickest:

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1