Scrolling through an array
the title of the question may be a bit missed, but I'm not sure how to describe my problem.
I want to restructure the keys of an array in such a way that the loop skips with the following pattern:
Example 1:
keys from 1,2,3,4,5,6,7,8,9 will lead to 1,9,5,3,7,2,6,4,8
- take the first element - 1
- take the last element - 9
- take average (1 + 9) / 2 = 5
- go to the first half and take the middle of 1 and 5 - 3
- go to the second half and take the middle of 5 and 9 - 7
- go back to the first half of the first half and take 2
- go back to the first half of the second half and take 6
- go back to the second half of the first half and take 4
- go back to the second half of the second half and take 8
Of course, this is an idealized example where everything is beautifully shared. If not, you need to fold and sink to separate the new elements.
Example 2:
key from 1,2,3,4,5,6,7,8,9,10 will lead to 1,10,5,6,3,8,2,7,4,9
With my little knowledge of the algorithm and data structures, I tried to use recursion / split and win, but I was unable to implement jumping between hemispheres.
So I think I need to add parameters such as the length of the separated halves of the positions, but here I am at a loss to implement.
Interesting question for me: I think this is difficult and is there a much easier solution? Or is this problem really difficult?
I'm glad for any advice on the ore version literature snippets to try.
Thanks and best wishes Stefan
source to share
I'm not sure if you can implement this algorithm using recursive or split and overcome. But you can do it elegantly using Breadth First Search. Below is python pseudocode where you have a queue whose elements are spans.
#initialize queue Q with the whole interval
n = len(your_list)
# breadth first search
Q.push([0, n-1])
while Q not empty:
itv = q.pop_front()
process(itv) # print the middle element of interval itv, etc.
itv_1, itv_2 = divide_interval_into_halves(itv)
if len(itv_1) > 0:
Q.push(itv_1)
if len(itv_1) > 0:
Q.push(itv_2)
Hope this helps :)
source to share