# Type-stable alternatives to Iterators.product?

**URL:** https://discourse.julialang.org/t/type-stable-alternatives-to-iterators-product/113790
**Category:** General Usage
**Tags:** iterators, combinatorics
**Created:** [May 3, 2024, 12:16pm UTC](https://discourse.julialang.org/t/type-stable-alternatives-to-iterators-product/113790 "2024-05-03T12:16:18Z")
**Posts on this page:** 3
**Page:** 1

<div class="post-metadata">

### Author: ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)
#### Post date: [May 3, 2024, 12:16pm UTC](https://discourse.julialang.org/t/type-stable-alternatives-to-iterators-product/113790/1 "2024-05-03T12:16:18Z")

</div>

I’m dealing with a combinatorial problem. Given N vectors of integers of varied lengths, I want to find all possible ways to select one integer from each vector. Here’s my code, which is unfortunately not type-stable:

```julia
julia> const data = [[1,2], [11,12], [101]];

julia> function all_combinations(a::Vector{Vector{Int}})
           combinations = Vector{Int}[]
           for c in Iterators.product(a...)
               push!(combinations, collect(c))
           end
           combinations
       end

julia> all_combinations(data)
4-element Vector{Vector{Int64}}:
 [1, 11, 101]
 [2, 11, 101]
 [1, 12, 101]
 [2, 12, 101]

```

Type instability is present according to the output of `@code_warntype all_combinations(data)`. Is there a neat way to rewrite the code in a type-stable manner? (Neither N nor the length of each vector is known at compile time.)

---

<div class="post-metadata">

### Author: ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)
#### Post date: [May 3, 2024, 12:21pm UTC](https://discourse.julialang.org/t/type-stable-alternatives-to-iterators-product/113790/2 "2024-05-03T12:21:25Z")

</div>

This works

```julia
function all_combinations(a)
    combinations = Vector{Int}[]
    for c in Iterators.product(a...)
        push!(combinations, collect(c))
    end
    combinations
end
data = ([1,2], [11,12], [101])

@code_warntype all_combinations(data)

```

The trick is that the `a...` operation is only type stable for things with known types and _length_!  
One way to make the length to be known at compile time is to use a `Tuple`.

---

<div class="post-metadata">

### Author: ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)
#### Post date: [May 3, 2024, 12:50pm UTC](https://discourse.julialang.org/t/type-stable-alternatives-to-iterators-product/113790/4 "2024-05-03T12:50:19Z")

</div>

I’ve come up with a type-stable solution when the input has unknown length:

```julia
function all_combinations(a::Vector{Vector{Int}})
    foldl(form_combinations, a, init = Vector{Int}[])
end

function form_combinations(a::Vector{Vector{Int}}, b::Vector{Int})
    if length(a) == 0
        [[i] for i in b]
    else
        [push!(copy(i), j) for i in a for j in b]
    end
end

```

Test:

```julia
julia> all_combinations([[1,2], [11, 12], [101]])
4-element Vector{Vector{Int64}}:
 [1, 11, 101]
 [1, 12, 101]
 [2, 11, 101]
 [2, 12, 101]

```