寻找一种更快的方法来帮助 reduce/create 一个巨大的字符串列表

Question

我试着写了一个算法来在游戏中猜对 "Masterminds",
它有效，平均猜测次数为 6，但计算最佳猜测需要花费大量时间。

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

Create the set S of 1296 possible codes (1111, 1112 ... 6665, 6666).

Start with initial guess 1122 (Knuth gives examples showing that other first guesses such as 1123, 1234 do not win in five tries on every code).

Play the guess to get a response of colored and white pegs.

If the response is four colored pegs, the game is won, the algorithm terminates.

Otherwise, remove from S any code that would not give the same response if the current guess were the code.

在我的代码中，第 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());

寻找一种更快的方法来帮助 reduce/create 一个巨大的字符串列表

looking for a faster way to help reduce/create a huge list of strings

c++

runtime

data-structures