What is the simplest way to access array (not vector) element from middle to outermost?

Question

I want to create a game, which monster is aligned from left to right horizontally, the order of monsters has other logical meaning (e.g.: the appearing sequence), but I want to play some effects which starts from the middle monster

the array, for example, for odd number size array:

int[] a=new int[]{1,2,3,4,5};

the access sequence is 3,2,4,1,5 (or 3,4,2,5,1)

for even number size array:

int[] a=new int[]{1,2,3,4,5,6};

the access sequence is 3,4,2,5,1,6 or (4,3,5,2,6,1)

If it is in something like vector in c++, it will be:

std::vector<int> a;
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
a.push_back(5);

while(a.size()>0){
    printf("%d\n",a[a.size()/2]);
    a.erase(a.begin()+a.size()/2);
}

which the output is

3
4
2
5
1

But I want an algorithm which is suitable to be used in array, which the position of element cannot be changed,

I tried something like:

int a[]={1,2,3,4,5};
for(int i=a.size()/2;i>=0 && i<a.size();i=XXXX){
    printf("%d\n",a[i]);
}

which XXXX is the update statement, which I still don't know what should it be.

In fact, I don't know if my init value and condition statement in for loop is correct. I even don't know if it can be done by a single loop.

Ok, I know I can have a temp vector and then copy the index to do that, but I also want to know if it can be done in a single for loop without any temp vector or array.

Can anyone help (or is there another simple algorithm to do that?)?

Answer 1

An algorithm to list the elements from innermost to outermost is to pull off the last and first entries (pop and shift) in the array in alternation until no elements are left, then reverse the list of what you have pulled off. This works for odd and even-length arrays naturally.

For example,

1,2,3,4,5,6
1,2,3,4,5       6
2,3,4,5         6,1
2,3,4           6,1,5
3,4             6,1,5,2
3               6,1,5,2,4
                6,1,5,2,4,3
                3,4,2,5,1,6  // Reversed list from above

and

1,2,3,4,5
1,2,3,4         5
2,3,4           5,1
2,3             5,1,4
3               5,1,4,2
                5,1,4,2,3
                3,2,4,1,5  // Reversed list from above

You can use this above algorithm to create an index map array which you can use to access your main array in the order you requested. For example:

// Start with an array of indices 
// from 0..arr.length-1
0,1,2,3,4
0,1,2,3         4
1,2,3           4,0
1,2             4,0,3
2               4,0,3,1
                4,0,3,1,2
                2,1,3,0,4  // Reversed list from above

Then you have a mapping array

int[] arr = new int[]{1,2,3,4,5};
int[] map = new int[]{2,1,3,0,4};

which you can use to access your main array, for example

arr[map[0]]; // returns 3

---

Edit: Added Java implementation and demo.

public static int[] creatIndexMap(int length) {

    // Create a deque so elements can be removed from both ends
    Deque<Integer> tmp = new LinkedList<Integer>();
    for(int i = 0; i < length; i++) {
        tmp.add(i);
    }

    // In alternation remove the last and first entries of tmp
    // and add them in reverse order to the map array
    int[] map = new int[length];
    int index = length-1;
    while (!tmp.isEmpty()) {
        // Remove last element
        map[index--] = (int) tmp.removeLast();

        // Remove first element
        if(!tmp.isEmpty()) {
            map[index--] = (int) tmp.removeFirst();
        }
    }
    return map;
}

Demo: IDEOne

Answer 2

This is an answer for the edited question that is language-agnostic and wants a single function to display the elements in the stated order.

First, chose a "middle" index.

var i = Math.floor((a.length-1)/2);

Then alternate right and left moving outwards incrementally until either edge of the array is encountered.

To facilitate this, start with a variable d = 0 which will be the distance from the middle element. This d will be updated like so upon each iteration

d += -(2*d) + (d > 0 ? 0 : 1);

with the below update pattern:

0, 1, -1, 2, -2, ...

If the middle index is 2 in array [1,2,3,4,5], then applying a[i + d] will result in

3, 4, 2, 5, 1

I hope this is what you are looking for.

---

Here is a JavaScript implementation:

var a = [1,2,3,4,5,7,8];

var i = Math.floor((a.length-1)/2);
for (var d = 0; i+d >= 0 && i+d < a.length;) {

  // Print out the value
  console.log(a[i + d]);

  // Outward-moving logic
  d += -(2*d) + (d > 0 ? 0 : 1);
}

or if you want this all in the for-loop like you've tried in your question, you can do this:

var a = [1,2,3,4,5,7,8];

var i = Math.floor((a.length-1)/2);
for (var d = 0; i+d >= 0 && i+d < a.length; d += -(2*d) + (d > 0 ? 0 : 1)) {
  console.log( a[i + d] ); // print the value
}

Result on [1,2,3,4,5] (odd-length array):

3 4 2 5 1

Result on [1,2,3,4,5,6,7,8] (even-length array):

4 5 3 6 2 7 1 8

Demo: JSBin