# Most minimal way to get breadth-first indices?

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

``````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.

``````# 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, ,

This is the best I could come up with:

``````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:

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

For an example of how this works:

``````> 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
]
``````

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

``````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:

``````> 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
]``````
``````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)
``````
1 Like

Functional version:

``````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.