While writing Naval Fight I wanted to have the easy computer opponent select a random position on the board grid every turn.

First I implemented a naive solution creating an array of all possible positions that would be randomly selected from, but after a selection was used it was removed from this array.

validPositions = gridPositions.clone();

// selection
position = validPositions[random() * validPositions.length];
validPositions.removeElement(position);

This solution was adequate, but there can always be improvements, and now that I am storing information in a second array, how can it be used more efficiently. Thinking about the problem further it became apparent that this was akin to listening to a playlist on shuffle. Which then gives the light bulb moment that instead of thinking about random selection with no repeats I should just shuffle the array of positions, just like having a deck of cards and removing a card for each turn, noting it’s value (ie: grid position).

After a little searching I came across the Fisher-Yates shuffle algorithm, and found an efficient and unbiased implementation:

// setup
int currentPosition = 0;

for (int i = gridPositions.length; i > 1; i--) {
  // Pick a random element to swap with the i-th element.
  int j = uniform_random() * i;
  // Swap elements.
  int tmp = gridPositions[j];
  gridPositions[j] = items[i-1];
  gridPositions[i-1] = tmp;
}

// selection on each turn
position = gridPositions[currentPosition++];

This solution generates an array of possible positions which are then shuffled, and finally an index into the array is stored where the next position can be read. Each time the position is accessed from the array this counter increases to always point at the next position. There are other solutions that would work, but this seems to be a good final solution for my problem.

</steve>