Q:

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

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!

A:

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

