Most minimal way to get breadth-first indices?

General Usage
1

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,

50%20PM,

2

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_indices = breadth_indices(length(cur_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
]
3

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
]
4 
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
5

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.