寻找更快的方法来帮助减少/创建庞大的字符串列表

Question

我试着写一个算法在游戏“Masterminds”中正确猜测， 它起作用的平均猜测次数为6，但计算最佳猜测需要花费大量时间。

我使用了Knuth的思想，算法的工作原理如下：

1. 创建12个可能代码的集合S（1111,1112 ... 6665,6666）。
2. 从最初的猜测1122开始（Knuth给出的例子显示其他第一次猜测，例如1123,1234在每次代码的五次尝试中都没有获胜）。
3. 玩猜测得到彩色和白色钉的响应。
4. 如果响应是四个彩色钉，则赢得游戏，算法终止。
5. 否则，如果当前猜测是代码，则从S中删除任何不会给出相同响应的代码。

在我的代码中，第2步是取随机数。

我为此使用了vector<string>。

AllPoss是充满字符串的向量，我猜是最后使用的猜测。 answer是公牛和奶牛的计数看起来像“x，y”（其中x和y是数字）

void bullpgia::SmartGuesser::remove(string guess, string answer)
{
    for (auto i= AllPoss.begin();i != AllPoss.end();i++){
        string token = *i;
        if (calculateBullAndPgia(token, guess) != answer)
        AllPoss.erase(i--);
    }
}

这是需要花费大量时间来计算的部分有没有改进的方法？

创建我使用的列表：

void bullpgia::SmartGuesser::All() {
    /**
     * creates a pool of all the possibilities strings
     * we then delete the ones we dont need
     * @param length is the length of the word we need to guess
     */
    for(int i=0;i<pow(10,length);i++){
        stringstream ss;
        ss << setw(length) << setfill('0') << i;
        string s = ss.str();
        AllPoss.push_back(s);
    }
}

函数calculateBullAndPgia（string，string）是：

string calculateBullAndPgia(const string &choice, const string &guess) {
    string temp = choice;
    string temp2 = guess;
    unsigned int bull = 0;
    unsigned int pgia = 0;
    for (int i = 0; i < temp.length(); i++) {
        if (temp[i] == temp2[i]) {
            bull++;
            temp[i] = 'a';
            temp2[i] = 'z';
        }
    }
    for (int i = 0; i < temp.length(); i++) {
        for (int j = 0; j < temp2.length(); j++) {
            if (i != j && temp[i] == temp2[j]) {
                pgia++;
                temp[i] = 'a';
                temp2[j] = 'z';
            }
        }
    }
    return to_string(bull) + "," + to_string(pgia);
}

Answer 1

擦除向量中间的单个元素是O（n）。我的猜测是你每次打电话给SmartGuesser::remove都会花费O（n）次。然后你循环，所以你可能有一个O（n ^ 3）算法。你可以使用std::remove_if，它是O（n），将所有被删除的元素移动到向量的末尾，在那里它们可以被廉价地擦除：

AllPoss.erase(std::remove_if(AllPos.begin(), AllPos.end(), [&](const std::string& token, const std::string& guess) { return calculateBullAndPgia(token, guess) != answer; }), AllPos.end());