# Finding array indices without creating an array using vectors?

**URL:** <https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125>\
**Category:** General Usage\
**Tags:** indexing\
**Created:** [February 27, 2021, 5:48am UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125 "2021-02-27T05:48:47Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![taeukseo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/taeukseo/32/21819_2.png) [@taeukseo](https://discourse.julialang.org/u/taeukseo)\
**Post date:** [February 27, 2021, 5:48am UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/1 "2021-02-27T05:48:47Z")

</div>

I apologize for the poor phrasing of the question - it sounds like an oxymoron!  
😐

I have been struggling to write a function `F` which, given:

1. vectors of sizes `N1, N2, N3`… etc
2. a number `1<= i <= N1 * N2 * N3`,

returns indices `x1, x2, x3`… etc. that correspond to i.

For example, assuming vectors

```julia
A = [1, 2], B = [3, 4], C = [5,6],

```

we can imagine a combined array `ABC`.

```julia
ABC = 1 3 5
        2 3 5
        1 4 5
        2 4 5
        1 3 6
        2 3 6
        1 4 6
        2 4 6

```

Then, given an input of `i = 2`, the elements on the second row in `ABC` are `[2,3,5]`.  
These correspond to `A[2] = 2, B[1] = 3, C[1] = 5`.

The function `F` would return the indices `2,1,1`. ie.

```julia
2,1,1 = F(2,A,B,C)

```

I was wondering if there were functions in Julia that can do the same job as the function that I described above? I am especially hoping to find indices without actually creating the array `ABC` to minimize memory use.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [February 27, 2021, 6:33am UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/2 "2021-02-27T06:33:10Z")

</div>

```julia
julia> function F(idx::Integer, arys...)
           res = zeros(Int, length(arys))
           for (i, A) in enumerate(arys)
              l = length(A)
              res[i] = mod1(idx, l)
              idx = cld(idx, l)
           end
           res
       end

```

I _think_ this does what you want, not 100% sure, my brain is small and it’s kinda late. The idea is to think of each array as n-bit counter. We start with the bit that cycles the quickest, find out how many times it cycled, use that cycle number for the next bit.

---

<div class="post-metadata">

**Author:** ![taeukseo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/taeukseo/32/21819_2.png) [@taeukseo](https://discourse.julialang.org/u/taeukseo)\
**Post date:** [February 27, 2021, 6:34am UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/3 "2021-02-27T06:34:50Z")

</div>

I have made a naive attempt by writing down a function as follows.

```julia
function returnIndex(index, N1, N2, N3)

    index0 = 1

    tmp10 = div(index - 0.05, index0)
    tmp11 = mod(tmp10, N1)
    A1 = convert(Int, floor(tmp11)) + 1
    index0 = index0*N1
    
    tmp20 = div(index-0.05, index0)
    tmp21 = mod(tmp20, N2)
    A2 = convert(Int, floor(tmp21)) + 1
    index0 = index0*N2
    
    tmp30 = div(index-0.05, index0)
    tmp31 = mod(tmp30, N3)
    A3 = convert(Int, floor(tmp31)) + 1
    index0 = index0*N3

    return A1, A2, A3
end

```

To make the code more generalizable, I have tried to write the code in a recursive format.

I was wondering if the above function is too expensive for computing?

Also, is there an easy way to let the function accept variable number of arguments?

---

<div class="post-metadata">

**Author:** ![taeukseo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/taeukseo/32/21819_2.png) [@taeukseo](https://discourse.julialang.org/u/taeukseo)\
**Post date:** [February 27, 2021, 6:36am UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/4 "2021-02-27T06:36:58Z")

</div>

> [@jling](#):
>
> ```julia
> res_T = promote_type(eltype.(arys)...)
> res = Vector{res_T}(undef, length(arys))
> for (i, A) in enumerate(arys)
> l = length(A)
> res[i] = mod1(idx, l)
> idx = cld(idx, l)
> end
> res
> end
> 
> ```

Thanks!! I will try out the code.

---

<div class="post-metadata">

**Author:** ![jules](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@jules](https://discourse.julialang.org/u/jules)\
**Post date:** [February 27, 2021, 6:58am UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/5 "2021-02-27T06:58:10Z")

</div>

I think this does what you want:

```julia
function f(i, vecs::AbstractVector...)
    cis = CartesianIndices(length.(vecs))
    ci = cis[i]
end

```

We pretend we have an n-dimensional array where each vector corresponds to one dimension, with `CartesianIndices` describing all indices of that array in a lazy manner. Then you can index with an integer into that and will get the CartesianIndex at that position.

```julia
julia> A = [1, 2]; B = [3, 4]; C = [5,6]
2-element Vector{Int64}:
 5
 6

julia> f(2, A, B, C)
CartesianIndex(2, 1, 1)

```

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [February 27, 2021, 10:18am UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/6 "2021-02-27T10:18:21Z")

</div>

Another possibility for collecting the indices sought, edited for variable number of input arrays:

```julia
function g(n, vecs...)
    it = [1:length(v) for v in vecs]
    collect(Iterators.product(it...))[n]
end

A = [1, 2]
B = [3, 4, 5]
C = [6, 7, 8, 9, 10]

julia> g(2, A, B, C)
(2, 1, 1)
julia> g(2, B, C)
(2, 1)
julia> g(2, B)
(2,)

```

Just noticed that this function runs out of memory for large arrays. For sake of understanding, could someone point out the issue(s)?  
Thanks in advance.

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [February 27, 2021, 1:15pm UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/7 "2021-02-27T13:15:47Z")

</div>

> [@rafael.guerra](#):
>
> `collect(Iterators.product(it...))[n]`

This creates an array that contains the Cartesian product of all the iterators. Only after that (possibly huge) array is created, does `[n]` extract one value from it.

You could do something like `first(Iterators.drop(Iterators.product(it...), n-1))` to avoid creating the array.

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [February 27, 2021, 3:46pm UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/8 "2021-02-27T15:46:42Z")

</div>

Is this for complete polynomials? If so, I remember seeing a function that did this in one of the related packages providing orthogonal polynomial utilities.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [February 27, 2021, 4:48pm UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/9 "2021-02-27T16:48:27Z")

</div>

> [@taeukseo](#):
>
> `convert(Int, floor(tmp11))`

```julia
floor(Int, tmp11) 

```

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [February 27, 2021, 6:38pm UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/10 "2021-02-27T18:38:12Z")

</div>

@sijo, thanks for the explanation, it makes sense. However, this function will be very slow for very large arrays.  
The direct computation by @jling seems to be more natural/a more direct solution.  
@jules’ elegant CartesianIndices solution ran into problems in the first example below, though. It’s as if the choice of the integer types for the array indices was not appropriate for their Cartesian product?

```julia
function f1(n::Integer, vecs...) # by @jling
    res = Vector{Int}(undef, length(vecs))
    @inbounds for i in eachindex(vecs)
        l = length(vecs[i])
       res[i] = mod1(n, l)
       n = cld(n, l)
    end
    res
end

function f2(n, vecs::AbstractVector...) # by @jules
    cis = CartesianIndices(length.(vecs))
    ci = cis[n]
end

using BenchmarkTools
A = randn(1_000_000);
B = randn(2_000_000);
C = randn(5_000_000);
@btime f1(11_000_000_000,$A,$B,$C) # 41 ns (1 allocation: 112 bytes)
@btime f2(11_000_000_000,$A,$B,$C) # ERROR: BoundsError: attempt to access 1000000×2000000×5000000

A = randn(10_000_000);
B = randn(20_000_000);
C = randn(50_000_000);
@btime f1(11_000_000_000,$A,$B,$C) # 43 ns (1 allocation: 112 bytes)
@btime f2(11_000_000_000,$A,$B,$C) # 310 ns (6 allocations: 192 bytes)

```

---

<div class="post-metadata">

**Author:** ![jules](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@jules](https://discourse.julialang.org/u/jules)\
**Post date:** [February 27, 2021, 6:57pm UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/11 "2021-02-27T18:57:42Z")

</div>

That’s probably because:

```julia
julia> 1_000_000 * 2_000_000 * 5_000_000
-8446744073709551616

```

The bounds check integer overflows. I don’t know if that’s worth an issue, because “real” arrays probably never have sizes that can cause that 🙂

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [February 27, 2021, 6:57pm UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/12 "2021-02-27T18:57:50Z")

</div>

```julia
julia> function f1(n, vecs...) # by @jling
           res = Vector{Int}(undef, length(vecs))
           @inbounds for i in eachindex(vecs) # this inbounds can already be inferred by compiler I think
              l = length(vecs[i])
              res[i] = mod1(n, l)
              n = cld(n, l)
           end
           res
       end
f1 (generic function with 1 method)

```

didn’t know we’re competing for last drop of performance but here’s a much faster version.

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [February 27, 2021, 7:08pm UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/13 "2021-02-27T19:08:09Z")

</div>

@jling, thank you. This is just for Julia learning purposes.

Fixed the code above with your new turbo version and given the new running times, I think logic finally prevailed.

---

<div class="post-metadata">

**Author:** ![taeukseo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/taeukseo/32/21819_2.png) [@taeukseo](https://discourse.julialang.org/u/taeukseo)\
**Post date:** [February 27, 2021, 7:46pm UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/14 "2021-02-27T19:46:09Z")

</div>

Ah! This was for parallelization of a grid search problem. I was trying to find values for each element of a large functional array.

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [February 27, 2021, 8:03pm UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/15 "2021-02-27T20:03:31Z")

</div>

BTW, hi Taeuk 😃

---

<div class="post-metadata">

**Author:** ![taeukseo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/taeukseo/32/21819_2.png) [@taeukseo](https://discourse.julialang.org/u/taeukseo)\
**Post date:** [February 27, 2021, 10:12pm UTC](https://discourse.julialang.org/t/finding-array-indices-without-creating-an-array-using-vectors/56125/16 "2021-02-27T22:12:56Z")

</div>

Hi Tyler! What a small world!! 😃