How to consume data from generator expression

New to Julia
1

Hi all,

I’m using Julia 1.5.2 and Combinatorics v1.0.2.

I tried the following combinatorics exercise.

First level:
Get all combinations selecting 4 elements out of 8 available elements, without repetition (meaning each element occurs only once).

using Combinatorics
julia> a = combinations(1:8,4)
Base.Generator{Combinatorics.Combinations,Combinatorics.var"#reorder#10"{UnitRange{Int64}}}(Combinatorics.var"#reorder#10"{UnitRange{Int64}}(1:8), Combinatorics.Combinations(8, 4))

julia> a_list = [x for x in a]
70-element Array{Array{Int64,1},1}:
 [1, 2, 3, 4]
 ...
 [5, 6, 7, 8]

Up to here, everything is fine.

Now let’s add a second level of complexity.
Just select n (e.g. 6) elements of these previously generated 70 elements and “process” them.

julia> b = combinations(combinations(1:8, 4), 6)
Base.Generator{Combinatorics.Combinations,Combinatorics.var"#reorder#10"{Base.Generator{Combinatorics.Combinations,Combinatorics.var"#reorder#10"{UnitRange{Int64}}}}}(Combinatorics.var"#reorder#10"{Base.Generator{Combinatorics.Combinations,Combinatorics.var"#reorder#10"{UnitRange{Int64}}}}(Base.Generator{Combinatorics.Combinations,Combinatorics.var"#reorder#10"{UnitRange{Int64}}}(Combinatorics.var"#reorder#10"{UnitRange{Int64}}(1:8), Combinatorics.Combinations(8, 4))), Combinatorics.Combinations(70, 6))

julia> b_list = [x for x in b]
ERROR: MethodError: no method matching getindex(::Base.Generator{Combinatorics.Combinations,Combinatorics.var"#reorder#10"{UnitRange{Int64}}}, ::Int64)
Stacktrace:
 [1] (::Combinatorics.var"#9#11"{Base.Generator{Combinatorics.Combinations,Combinatorics.var"#reorder#10"{UnitRange{Int64}}}})(::Int64) at .\none:0
 [2] iterate at .\generator.jl:47 [inlined]
 [3] collect at .\array.jl:686 [inlined]
 [4] reorder at C:\Users\mac\.julia\packages\Combinatorics\Udg6X\src\combinations.jl:48 [inlined]
 [5] iterate at .\generator.jl:47 [inlined]
 [6] iterate at .\generator.jl:44 [inlined]
 [7] collect(::Base.Generator{Base.Generator{Combinatorics.Combinations,Combinatorics.var"#reorder#10"{Base.Generator{Combinatorics.Combinations,Combinatorics.var"#reorder#10"{UnitRange{Int64}}}}},typeof(identity)}) at .\array.jl:686
 [8] top-level scope at REPL[11]:1

Background:
In this example, there are 70 possible 4 element long vectors. I want to evaluate all combination of each e.g. 6 of these 4 element vectors selected from the 70 possible ones, by a function qualifying each arrangement (with a sort of costfunction). This sort of list comprehension above it just to show my basic problem. Nearly the same issue occurs, when calling the costfunction for each b element in a for loop consuming the generator data.

Obviously I did not yet understand the generator concept fully.

I did not find any examples in the Web pointing me to a solution for this exercise.
The reported error it-self, does not guide me enough to a solution. Why is it working in the first step, but not in the more complex one.

Has anybody an example and much better, also an explanation on how to consume such generated data.

Thanks a lot in advance,

Mike

2

From the combinations help

combinations(a, n)

Generate all combinations of n elements from an indexable object a. Because the number of combinations can be very large, this function returns an iterator object. Use
collect(combinations(a, n)) to get an array of all combinations.

When you are calling combinations(combinations(1:8, 4), 6) internal combinations(1:8, 4) is not an indexable object, because it is a generator. You have to materialize it in order to get the result. By the way it is better to use collect, instead of [x for x in b]

julia> a = collect(combinations(1:8, 4))  # materialization part, now `a` is an Array, which can be indexed
70-element Array{Array{Int64,1},1}:
 [1, 2, 3, 4]
 [1, 2, 3, 5]
 ⋮

julia> b = combinations(a, 6) # it's better not to collect this one, since it has 94 billions elements, if I am correct
2 Likes
3

Thanks a lot for this quick response. In principle, I did also try to use collect in all variants (inner, outer and both arrays).

Obviously I did not recognize, that your solution, I also already tried, did already the job of processing.
Since I tried the following:

a = collect(combinations(1:8, 4)) 
b = combinations(a, 30)

It has been processed, but no idea how fast and how far. So I stopped the processing.

The length of b could not be determined anymore. So no idea, if processing would end in this life.
The expected element count will be rather large, ~5.5E+19.
I asumed that something was wrong with the generator expression.

Is there a way to process such lists and allow tracking the progress of processing, even though the total number can not derived from the generator expression anymore.

4

Everything is possible :slight_smile: Not everything is useful though.

First of all, if you want to get track of what is going on with your generator, you can use either ProgressMeter.jl or TerminalLoggers.jl or any other similar package. I’ll show how it can be done using ProgressMeter.jl

If your number of calculations is reasonably small (like in case of combinations(a, 6)) it is super simple to do

using Combinatorics
using ProgressMeter

a = collect(combinations(1:8, 4))
res =[]
@showprogress for x in combinations(a, 6)
  push!(res, x)
end

For combinations(a, 30) this trick wouldn’t work, since you’ll get OverflowError: binomial(70, 30) overflows. In this case you can update progressmeter manually.

using Combinatorics
using ProgressMeter
using SpecialFunctions

a = collect(combinations(1:8, 4)) 
n = Int64(round(70/(30*40) * 1/beta(30, 40))/10)  # I divided n by 10, because `progress` does not support Int128, so I'll update only each 10th tick

p = Progress(n, barlen = 60)
res = 0. # I switched to other operation, since I do not have enough memory to keep all possible combinations. It doesn't affect idea itself.

cnt = 1
for x in combinations(a, 30)
    res += length(x)
    if cnt == 10
        next!(p)
        cnt = 1
    else
        cnt += 1
    end
end

Well, now progress tells me that it’ll finish calculations in ETA: 159651143.80 days. I highly doubt we’ll be around to see the result :slight_smile: So maybe you should solve your original task (that which require combinations of combinations) in somewhat different way.

1 Like
5

Thanks again Andrey for your reply.

I already worried about, that the brute force way of processing, would not be feasible at all.
Now I think it more than clear, that I have to solving my problem in a more intelligent way.
Hopefully I find some symmetry or redundancy in the sets to reduce complexity by factors.

But anyhow, your answers and tips are really appreciated. Further more the response time. :smiley:

Thanks again for your time!

1 Like