# Most minimal way to get breadth-first indices?

**URL:** <https://discourse.julialang.org/t/most-minimal-way-to-get-breadth-first-indices/12661>\
**Category:** General Usage\
**Tags:** question\
**Created:** [July 26, 2018, 2:25am UTC](https://discourse.julialang.org/t/most-minimal-way-to-get-breadth-first-indices/12661 "2018-07-26T02:25:17Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![djsegal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/djsegal/32/13752_2.png) [@djsegal](https://discourse.julialang.org/u/djsegal)\
**Post date:** [July 26, 2018, 2:25am UTC](https://discourse.julialang.org/t/most-minimal-way-to-get-breadth-first-indices/12661/1 "2018-07-26T02:25:17Z")

</div>

Let’s say you have N integers from 1:N (i.e. N = 15)

```julia
cur_vector = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

```

What is the most minimal way to turn this into the breadth-first search indices from recursive bisection?

i.e.

```julia
# assuming a breadth_indices func
> println( breadth_indices( cur_vector ) )

[8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]

```

* * *

Pictorially,

![50%20PM](https://global.discourse-cdn.com/julialang/original/3X/8/4/84a71d5628aedf0c41e13cfb66db101df88bef19.png),

---

<div class="post-metadata">

**Author:** ![djsegal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/djsegal/32/13752_2.png) [@djsegal](https://discourse.julialang.org/u/djsegal)\
**Post date:** [July 26, 2018, 2:42am UTC](https://discourse.julialang.org/t/most-minimal-way-to-get-breadth-first-indices/12661/2 "2018-07-26T02:42:39Z")

</div>

This is the best I could come up with:

```julia
function breadth_indices(num_points::Number)
  cur_indices = []

  cur_step = num_points
  while length(cur_indices) < num_points - 1
    cur_step = Int(floor( (cur_step-1) / 2 )) + 1

    for cur_index in 1:num_points-1
      iszero( cur_index % cur_step ) || continue
      in(cur_index, cur_indices) && continue
      push!(cur_indices, cur_index)
    end
  end
  push!(cur_indices, num_points)

  cur_indices
end

```

* * *

Then you can have fun with it, by reordering vectors:

```julia
function bisect_reorder!(cur_vector::Vector)
  cur_indices = breadth_indices(length(cur_vector))
  cur_vector .= cur_vector[cur_indices]
end

```

For an example of how this works:

```julia
> cur_points = collect( linspace(0, 1, 11) )
> bisect_reorder!(cur_points)

[
 0.5
 0.2
 0.8
 0.1
 0.3
 0.7
 0.9
 0.0
 0.4
 0.6
 1.0
]

```

---

<div class="post-metadata">

**Author:** ![djsegal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/djsegal/32/13752_2.png) [@djsegal](https://discourse.julialang.org/u/djsegal)\
**Post date:** [July 26, 2018, 3:18am UTC](https://discourse.julialang.org/t/most-minimal-way-to-get-breadth-first-indices/12661/3 "2018-07-26T03:18:53Z")

</div>

A sister function of this would be your outward-in reordering:

```julia
function out_in_reorder!(cur_vector::Vector)
  cur_indices = centering_indices(length(cur_vector))
  cur_vector .= cur_vector[cur_indices]
end

function centering_indices(num_points::Number)
  cur_indices = []

  cur_half_point = Int(floor(num_points/2))
  for cur_index in 1:cur_half_point
    push!(cur_indices, cur_index)
    push!(cur_indices, num_points-(cur_index-1))
  end
  isodd(num_points) && push!(cur_indices, cur_half_point+1)

  cur_indices
end

```

* * *

An analogous example to the one above is:

```julia
> cur_points = collect( linspace(0, 1, 11) )
> out_in_reorder!(cur_points)

[
 0.0
 1.0
 0.1
 0.9
 0.2
 0.8
 0.3
 0.7
 0.4
 0.6
 0.5
]
```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [July 26, 2018, 7:56am UTC](https://discourse.julialang.org/t/most-minimal-way-to-get-breadth-first-indices/12661/4 "2018-07-26T07:56:30Z")

</div>

```julia
function collect_bisection_indexes!(ix, level, a, b)
    a ≤ b || return
    mid = (a+b) ÷ 2
    push!(ix, level => mid)
    collect_bisection_indexes!(ix, level + 1, a, mid - 1)
    collect_bisection_indexes!(ix, level + 1, mid + 1, b)
end

function bisection_indexes(n)
    ix = Vector{Pair{Int,Int}}()
    sizehint!(ix, n)
    collect_bisection_indexes!(ix, 0, 1, n)
    last.(sort!(ix, by = first))
end

bisection_indexes(15)

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [July 26, 2018, 9:45am UTC](https://discourse.julialang.org/t/most-minimal-way-to-get-breadth-first-indices/12661/5 "2018-07-26T09:45:46Z")

</div>

Functional version:

```julia
function collect_bisection_indexes(level, a, b)
    a ≤ b || return Vector{Tuple{Int,Int}}()
    mid = (a+b) ÷ 2
    vcat([level => mid],
         collect_bisection_indexes(level + 1, a, mid - 1),
         collect_bisection_indexes(level + 1, mid + 1, b))
end

function bisection_indexes(n)
    ix = collect_bisection_indexes(0, 1, n)
    last.(sort!(ix, by = first))
end

```

Implicitly, both of the above implementations rely on `sort!` choosing a stable algorithm, which I believe it does, but it could be made explicit.