Random Selection without Repeat (aka Shuffle)

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

The initial naive solution I implemented initially for testing was to have the computer choose a grid position at random checking to make sure it is a valid position, valid meaning that it had not been used before.

do {
position = gridPositions [ random() * N ];
} while ( ! valid(position) );

After testing on the iPhone device it became apparent that this was terribly inefficient, and it was possible this loop could continue indefinitely. The next iteration I used 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 = 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>