# Sorted product of infinite iterators

**URL:** <https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755>\
**Category:** General Usage\
**Created:** [June 14, 2022, 3:00pm UTC](https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755 "2022-06-14T15:00:18Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [June 14, 2022, 3:00pm UTC](https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755/1 "2022-06-14T15:00:18Z")

</div>

I have a collection of (potentially infinite) sorted iterators `I1`, `I2`, `I3`, … and a nondecreasing value function `sort_by((x1, x2, x3, ...))`. I want the sorted cartesian product of these iterators.

I’m thinking I can do this with a heap (adding a set may in certain edge cases result in a speedup), but I want to see if anyone else already has already implemented a solution to this problem.

(If `I1` and `I2` are the naturals and `sort_by` is `+`, then this provides a constructive proof that `N x N` is countable.)

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [June 14, 2022, 4:12pm UTC](https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755/2 "2022-06-14T16:12:46Z")

</div>

I’m a little unclear on what you mean by “sorted iterators” and “sorted product” - sorted by what metric, respectively?

If I understand correctly, `sorted_by` is your metric and you want the values (i.e. the tuples) produced by the iterators if you were to iterate them simultaneously to be sorted by that metric?

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [June 14, 2022, 7:16pm UTC](https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755/3 "2022-06-14T19:16:16Z")

</div>

For finite iterators, by sorted I mean `issorted(I)` returns true. By sorted by sorted\_by I mean `issorted(product, bt=sorted_by)` returns true. For infinite iterators I mean every prefix is sorted.

I want a result that is equivalent to `sort(vec(collect(product(I1, I2, I3, ...))), by=sorted_by)` but without `collect`ing.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [June 14, 2022, 7:18pm UTC](https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755/4 "2022-06-14T19:18:47Z")

</div>

I don’t think there is a good way to do this algorithmically. pretty much any good sorting algorithm will need to collect the data.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [June 14, 2022, 7:32pm UTC](https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755/5 "2022-06-14T19:32:46Z")

</div>

We can assume that the input iterators are sorted and sorted\_by is nondecreasing, so we know that the first element of the output should be the first elements of the inputs. I think heapsort can get n log n in this case.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [June 14, 2022, 7:37pm UTC](https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755/6 "2022-06-14T19:37:38Z")

</div>

You don’t mean `product` then. The output of `product` is tuples with one entry from each iterator.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [June 14, 2022, 9:50pm UTC](https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755/7 "2022-06-14T21:50:37Z")

</div>

Sorry, `sorted_by` accepts a tuple, not three arguments. I’ve added a set of parentheses in my OP to reflect this.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [June 15, 2022, 6:01pm UTC](https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755/8 "2022-06-15T18:01:30Z")

</div>

I’ve implemented it. The important bits are in the implementation of the two-argument `iterate`. I’ve included a bit more for context, and you can see the complete package [here](https://github.com/LilithHafner/SortedIteratorProducts.jl/blob/4f8dbad2d189852b3287f41bf436dbb8c0aa7ba1/src/SortedIteratorProducts.jl#L54).

```julia
function SortedIteratorProduct(by::Function, iterators...)
    sources = cached.(iterators)
    SortedIteratorProduct(sources, by)
end

lookup(sip, x) = tuple((s[i] for (s, i) in zip(sip.sources, x))...)
function Base.iterate(sip::SortedIteratorProduct)
    all(x -> checkbounds(Bool, x, 1), sip.sources) || return nothing
    one = map(_->1, sip.sources)
    iterate(sip, (Set((one,)), BinaryHeap(Base.By(x -> (sip.by(lookup(sip, x)), reverse(x))), [one])))
end
function Base.iterate(sip::SortedIteratorProduct, (set, heap))
    isempty(heap) && return nothing
    indices = pop!(heap)

    for i in eachindex(indices)
        new = ntuple(j -> indices[j] + (j == i), length(indices))
        if checkbounds(Bool, sip.sources[i], indices[i]+1) && new ∉ set
            push!(set, new)
            push!(heap, new)
        end
    end
    lookup(sip, indices), (set, heap)
end

```

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [June 15, 2022, 7:38pm UTC](https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755/9 "2022-06-15T19:38:47Z")

</div>

Nice! With a bit more bookkeeping you can discard items from `set` once everything immediately higher in each direction is in `set`. That is, only keep the frontier. I assume this would typically save n^{1/d} memory.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [June 15, 2022, 7:57pm UTC](https://discourse.julialang.org/t/sorted-product-of-infinite-iterators/82755/10 "2022-06-15T19:57:10Z")

</div>

Thanks! I think that would work. My use case is not sensitive to space complexity, so I won’t bother, but I’ll [write it down](https://github.com/LilithHafner/SortedIteratorProducts.jl/issues/1) just in case.