从一组中随机挑选的快速方法,每个条目只挑选一次？

Question

我正在研究一个解决n皇后问题的程序(将n个国际象棋皇后放在一个n x n棋盘上的问题,这样他们都不能使用标准国际象棋女王的动作捕捉任何其他棋子).我正在使用启发式算法,它首先在每行中放置一个女王并从尚未占用的列中随机挑选一列.我觉得这一步是优化的机会.这是代码(在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);
    }

如果从代码中不清楚:我首先构建一个包含每列整数的向量.然后,对于每一行,我在向量中选择一个随机条目,将其值分配给该行的条目chboard[].然后我从向量中删除该条目,因此它不适用于任何其他皇后.

我很好奇可以使用数组和指针而不是向量的方法.还是<list>s？除了for循环之外,是否有更好的方法顺序填充向量？我很乐意听到一些建议!

Answer 1

以下内容应满足您的需求:

#include <algorithm>

...

int randplace[size];

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

random_shuffle(randplace, randplace + size);

如果你愿意的话,你也可以用矢量做同样的事情.

资料来源:http://gethelp.devx.com/techtips/cpp_pro/10min/10min1299.asp