Fast way to pick randomly from a set, with each entry picked only once?

Question

I'm working on a program to solve the n queens problem (the problem of putting n chess queens on an n x n chessboard such that none of them is able to capture any other using the standard chess queen's moves). I am using a heuristic algorithm, and it starts by placing one queen in each row and picking a column randomly out of the columns that are not already occupied. I feel that this step is an opportunity for optimization. Here is the code (in C++):

 vector<int> colsleft;

 //fills the vector sequentially with integer values
 for (int c=0; c < size; c++)
  colsleft.push_back(c);

 for (int i=0; i < size; i++)
 {
  vector<int>::iterator randplace = colsleft.begin() + rand()%colsleft.size();

  /* chboard is an integer array, with each entry representing a row
  and holding the column position of the queen in that row */

  chboard[i] = *randplace;
  colsleft.erase(randplace);
 }

If it is not clear from the code: I start by building a vector containing an integer for each column. Then, for each row, I pick a random entry in the vector, assign its value to that row's entry in chboard[]. I then remove that entry from the vector so it is not available for any other queens.

I'm curious about methods that could use arrays and pointers instead of a vector. Or <list>s? Is there a better way of filling the vector sequentially, other than the for loop? I would love to hear some suggestions!

Answer 1

Couple of random answers to some of your questions :):

1. As far as I know, there's no way to fill an array with consecutive values without iterating over it first. HOWEVER, if you really just need consecutive values, you do not need to fill the array - just use the cell indices as the values: a[0] is 0 and a[100] is 100 - when you get a random number, treat the number as the value.
2. You can implement the same with a list<> and remove cells you already hit, or...
3. For better performance, rather than removing cells, why not put an "already used" value in them (like -1) and check for that. Say you get a random number like 73, and a[73] contains -1, you just get a new random number.
4. Finally, describing item 3 reminded me of a re-hashing function. Perhaps you can implement your algorithm as a hash-table?

Answer 2

The following should fulfill your needs:

#include <algorithm>

...

int randplace[size];

for (int i = 0; i < size; i ++)
    randplace[i] = i;

random_shuffle(randplace, randplace + size);

You can do the same stuff with vectors, too, if you wish.

Source: http://gethelp.devx.com/techtips/cpp_pro/10min/10min1299.asp

Answer 3

Your colsleft.erase(randplace); line is really inefficient, because erasing an element in the middle of the vector requires shifting all the ones after it. A more efficient approach that will satisfy your needs in this case is to simply swap the element with the one at index (size - i - 1) (the element whose index will be outside the range in the next iteration, so we "bring" that element into the middle, and swap the used one out).

And then we don't even need to bother deleting that element -- the end of the array will accumulate the "chosen" elements. And now we've basically implemented an in-place Knuth shuffle.