# Iterating over integer simplex
**URL:** https://discourse.julialang.org/t/iterating-over-integer-simplex/135060
**Category:** Numerics
**Tags:** question, iterators, combinatorics
**Created:** [January 14, 2026, 3:48pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060 "2026-01-14T15:48:40Z")
**Posts on this page:** 15
**Page:** 1
### Author:  [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)
#### Post date: [January 14, 2026, 3:48pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/1 "2026-01-14T15:48:40Z")
I need to iterate over all `K`-tuples of nonnegative `Int`s that sum to `N`.
Eg if K is 3 and N==3,
```julia-auto
(0,0,3)
(0,1,2)
(0,2,1)
(0,3,0)
(1,0,2)
(1,1,1)
(1,2,0)
(2,0,1)
(2,1,0)
(3,0,0)
```
Ordering does not matter, just full traversal. I need this to be allocation free though.
At the moment, I am not even sure of the algorithm that I would use, so any hints on anything between that and “package X does this” would be helpful.
---
### Author:  [@adienes](https://discourse.julialang.org/u/adienes)
#### Post date: [January 14, 2026, 4:36pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/2 "2026-01-14T16:36:34Z")
do you need it specifically as an iterator? or would a `foreach_tuple(f::Function, N, K)` pattern be sufficient
---
### Author:  [@adienes](https://discourse.julialang.org/u/adienes)
#### Post date: [January 14, 2026, 4:53pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/4 "2026-01-14T16:53:37Z")
well, my bid is
```julia-auto
@generated function foreach_integer_simplex(f::F, N::Int, ::Val{K}) where {F, K}
if K == 1
return :(f((N,)))
end
syms = [Symbol(:i_, d) for d in (K-1):-1:1]
quote
s = 0
Base.Cartesian.@nloops $(K-1) i d -> 0:(N - s) d -> (s += i_d) d -> (s -= i_d) begin
remainder = N - s
val = ( $(syms...), remainder)
f(val)
end
end
end
julia> foreach_integer_simplex(3, Val{3}()) do t println(t) end
(0, 0, 3)
(0, 1, 2)
(0, 2, 1)
(0, 3, 0)
(1, 0, 2)
(1, 1, 1)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
(3, 0, 0)
```
---
### Author:  [@sgaure](https://discourse.julialang.org/u/sgaure)
#### Post date: [January 14, 2026, 4:55pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/5 "2026-01-14T16:55:55Z")
There are some algorithms here: [https://jjj.de/fxt/fxtbook.pdf#chapter.16](https://jjj.de/fxt/fxtbook.pdf#chapter.16)
And there’s an iterator in [SmallCombinatorics.jl · SmallCombinatorics.jl](https://matthias314.github.io/SmallCombinatorics.jl/stable/#SmallCombinatorics.partitions) which generates all the partitions, I suppose you can combine it with `permutations` in the same package, and filter out identitcal permutations. Or perhaps @matthias314 has something up his sleeve?
---
### Author:  [@matthias314](https://discourse.julialang.org/u/matthias314)
#### Post date: [January 14, 2026, 5:49pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/6 "2026-01-14T17:49:22Z")
The function [`weakcompositions`](https://matthias314.github.io/SmallCombinatorics.jl/stable/#SmallCombinatorics.weakcompositions) from SmallCombinatorics.jl gives what you want:
```julia-auto
julia> using SmallCombinatorics, Chairmarks
julia> weakcompositions(3, 3) |> collect
10-element Vector{SmallVector{16, Int8}}:
[0, 0, 3]
[0, 1, 2]
[0, 2, 1]
[0, 3, 0]
[1, 0, 2]
[1, 1, 1]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
[3, 0, 0]
julia> n = 3; k = 3; @b sum(first, weakcompositions($n, $k))
41.263 ns
```
The difference to @adienes’ solution is that the `k` parameter is not a
`Val`.
EDIT: Also, it’s an iterator, and it’s slower than @adienes’s code, see below.
---
### Author:  [@adienes](https://discourse.julialang.org/u/adienes)
#### Post date: [January 14, 2026, 6:13pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/7 "2026-01-14T18:13:41Z")
> [@matthias314](#):
>
> The difference to @adienes’ solution is that the `k` parameter is not a
> `Val`.
also this 😉
```julia-auto
julia> mutable struct Accumulator x::Int end
julia> add!(acc::Accumulator, y) = (acc.x += y)
add! (generic function with 1 method)
julia> const acc = Accumulator(0)
Accumulator(0)
julia> @b foreach_integer_simplex(Base.Fix1(add!, acc) ∘ sum, 8, Val{8}())
3.595 μs
julia> @b foreach(Base.Fix1(add!, acc) ∘ sum, weakcompositions(8, 8))
19.792 μs
```
---
### Author:  [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)
#### Post date: [January 14, 2026, 10:44pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/8 "2026-01-14T22:44:03Z")
another package which does the job:
```julia-auto
julia> using Combinat
julia> collect(Compositions(3,3;min=0))
10-element Vector{Vector{Int64}}:
[0, 0, 3]
[0, 1, 2]
[0, 2, 1]
[0, 3, 0]
[1, 0, 2]
[1, 1, 1]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
[3, 0, 0]
```
---
### Author:  [@matthias314](https://discourse.julialang.org/u/matthias314)
#### Post date: [January 14, 2026, 10:54pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/9 "2026-01-14T22:54:36Z")
> [@Jean\_Michel](#):
>
> `julia> using Combinat`
I think the OP is looking for an allocation-free solution. That would not be the case with Combinat.jl.
---
### Author:  [@karei](https://discourse.julialang.org/u/karei)
#### Post date: [January 15, 2026, 2:23am UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/10 "2026-01-15T02:23:00Z")
My idea is to enumerate starting from 0 and, after each increment by 1, check whether the sum of the digits equals N; if it does, I print it. This implementation has only a single allocation and runs very fast.
```julia
using StaticArrays
function odometer_inc_for!(d::MVector{K,Int}, ∑::Int) where {K}
@inbounds for i = 1:K
d[i] += 1
∑ += 1
if d[i] != 10
return ∑, false
end
d[i] = 0
∑ -= 10
end
return ∑, true # overflow
end
function scan_scheme1(::Val{K}, N::Integer) where {K}
d = zeros(MVector{K,Int})
∑ = 0
overflow = false
while !overflow
if ∑ == N
t = ntuple(i -> Int(d[K-i+1]), Val(K))
println(t)
end
∑, overflow = odometer_inc_for!(d, ∑)
end
nothing
end
scan_scheme1(Val(3), 3)
```
---
### Author:  [@matthias314](https://discourse.julialang.org/u/matthias314)
#### Post date: [January 15, 2026, 2:44am UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/11 "2026-01-15T02:44:44Z")
It doesn’t seem to be fast for larger inputs:
```julia-auto
julia> const acc = Accumulator(0); # as before
julia> @b foreach_integer_simplex(Base.Fix1(add!, acc) ∘ first, 8, Val{8}())
6.769 μs
julia> @b sum(first, weakcompositions(8, 8))
20.865 μs
julia> @b scan_scheme2(Base.Fix1(add!, acc) ∘ first, Val{8}(), 8)
238.037 ms (1 allocs: 80 bytes, without a warmup)
```
Here I’m using a modification that takes a function as first argument:
```julia-auto
function scan_scheme2(f::F, ::Val{K}, N::Integer) where {F,K}
d = zeros(MVector{K,Int})
∑ = 0
overflow = false
while !overflow
if ∑ == N
t = ntuple(i -> Int(d[K-i+1]), Val(K))
f(t)
end
∑, overflow = odometer_inc_for!(d, ∑)
end
nothing
end
```
---
### Author:  [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)
#### Post date: [January 15, 2026, 1:14pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/12 "2026-01-15T13:14:11Z")
> [@Tamas\_Papp](#):
>
> just full traversal. I need this to be allocation free though.
Maybe you should clarify/relax this assumption.
First of all, your desired API probably needs to pass `K` as `Val{K}()`: Otherwise the return type of the iteration is not inferred, and you get dynamic dispatch and the tuple needs to be allocated itself.
One reasonable API is `iterate_over_tuples(K,N) do the_tuple; ... end`. This automatically introduces a function barrier to make the thing type stable. And it makes recursive implementations much simpler. But you probably can expect an allocation, due to the passing of an uninferred function barrier.
If you don’t want this, then `K` must be known at the callsite as a type. I.e. the user needs to have received `::Val{K}` is its input already.
If you already explicitly construct / pass around `::Val{K}` somewhere, why not have a small re-usable helper structure `mutable struct IterationHelper{K, IntType} N::IntType ... end` that is allocated but re-usable, and has some internal scratch space? That simplifies the task a lot!
I think “no allocations” is too hard of an ask; and plainly not what you actually need. A better ask would be:
1. The amount of heap-allocated memory is `O(K*log(N))`, i.e. comparable to boxing the first output of the iterator, independent of the number of output tuples produced.
2. Appropriate re-use of data-structures can run this for many different N in the same size-class (Int8, Int16, Int32, Int64, Int128) without additional allocations, independent of the number of different n.
---
### Author:  [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)
#### Post date: [January 15, 2026, 1:42pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/13 "2026-01-15T13:42:52Z")
> [@foobar\_lv2](#):
>
> your desired API probably needs to pass `K` as `Val{K}()`: Otherwise the return type of the iteration is not inferred
That was implied, I have been using Julia for a decade now. 😉
> [@foobar\_lv2](#):
>
> I think “no allocations” is too hard of an ask; and plainly not what you actually need.
Not at all. After I slept on it, it turned out to be particularly simple:
```julia
"""
Generate the next item in the sequence of all `(i1, i2, ...)::NTuple{K,Int}` such that
`m ≥ i1 ≥ … ≥ 0`, ordered lexicographically using `>`.
NOTE: the invariant is not maintained if you start with `(m, m, …, m)`.
"""
function __inc(m::Int, i1::Int, iτ::Int...)
if i1 < m
(i1 + 1, iτ...)
else
iτ′ = __inc(m, iτ...)
(first(iτ′), iτ′...)
end
end
__inc(m::Int, i1::Int) = (i1 + 1,)
__diff(i1::Int, iτ::Int...) = (i1 - first(iτ),__diff(iτ...)...)
__diff(i1::Int) = i1
struct IntegerSimplex{K}
m::Int
function IntegerSimplex{K}(m::Int) where K
@assert K ≥ 1
@assert m ≥ 0
new{K}(m)
end
end
Base.length(itr::IntegerSimplex{K}) where K = binomial(itr.m + K - 1, K - 1)
Base.eltype(::IntegerSimplex{K}) where K = NTuple{K,Int}
function Base.iterate(itr::IntegerSimplex{K}, ι = ntuple(_ -> 0, Val(K-1))) where K
(; m) = itr
last(ι) > m && return nothing
ι′ = __inc(itr.m, ι...)
__diff(m, ι...), ι′
end
```
Eg
```julia
julia> @allocated mapreduce(sum, +, IntegerSimplex{3}(2))
0
```
Thanks for everyone who has answered! The key to my simple solution is to use a sequence `m >= i1 >= ...` internally, and then first difference it. This is much easier to keep track of when incrementing indices than working directly with the desired result (which is also doable, but I found it very confusing).
---
### Author:  [@matthias314](https://discourse.julialang.org/u/matthias314)
#### Post date: [January 15, 2026, 5:10pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/14 "2026-01-15T17:10:16Z")
> [@foobar\_lv2](#):
>
> your desired API probably needs to pass `K` as `Val{K}()`: Otherwise the return type of the iteration is not inferred
With SmallCombinatorics.jl the return type is inferred without `Val(K)` (and is some [`SmallVector`](https://matthias314.github.io/SmallCollections.jl/stable/smallvector/#SmallCollections.SmallVector)).
> [@Tamas\_Papp](#):
>
> The key […] is to use a sequence `m >= i1 >= ...` internally
That’s also what `SmallCombinatorics.weakcompositions` does internally.
---
### Author:  [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)
#### Post date: [January 16, 2026, 11:18am UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/15 "2026-01-16T11:18:00Z")
> [@matthias314](#):
>
> With [SmallCombinatorics.jl](https://juliaregistries.github.io/General/packages/redirect_to_repo/SmallCombinatorics) the return type is inferred without `Val(K)` (and is some [`SmallVector`](https://matthias314.github.io/SmallCollections.jl/stable/smallvector/#SmallCollections.SmallVector)).
Yes, I see, it is very clever design, basically restricted to a “large enough” `SmallVector`.
> [@matthias314](#):
>
> That’s also what `SmallCombinatorics.weakcompositions` does internally.
I think I will end up using that package, like SmallCollections.jl it looks very well designed. But figuring this out was fun 😉
---
### Author:  [@rveltz](https://discourse.julialang.org/u/rveltz)
#### Post date: [January 16, 2026, 12:29pm UTC](https://discourse.julialang.org/t/iterating-over-integer-simplex/135060/16 "2026-01-16T12:29:59Z")
`Iterators.product((0:10 for _= 1:3)...)`