开发者

Recursive function calls - generate permutations and backtracking

I have a vector of strings, all of the same size.

I have to build as a solution a list of strings that fulfill some conditions.

The pseudo code algorithm would be something like this:

backtrack(N)
if solution_valid()
    print solution
else
    for each word in vector
        if(possible candidate)
           backtrack(N+1)

I get lost in how to actually write the code.

I do not understand how to save current solutions, what 开发者_如何学Ckind of parameters to pass to the function...

Here is something I have though I think it's completely wrong:

int backtrack(vector<string> &dictionary, vector<string> &solution, int current_row)
{
cout << "current row: "<< current_row <<  " of: " << rows << endl;
if(current_row == rows /*&& square_completed(solution)*/)
{
    vector<string>::iterator word;
    for(word = solution.begin(); word != solution.end(); ++word)
    {
        cout << *word << endl;

    }
    return 0;
}

vector<string>::iterator word;
for(word = dictionary.begin(); word != dictionary.end(); ++word)
{
    backtrack(dictionary,solution,current_row+1);
    solution.push_back(*word);


}

return 1;

}

problem is that solution keeps growing without control. Could you tell me how to deal with it? and do a proper backtracking?


One problem is that you modify dictionary while iterating over it. Modifying a vector invalidates iterators of that vector, so word is no longer valid when you use it the next time. This might crash or otherwise fail. But the erase function returns a new valid iterator, you can use that to continue iterating.

Also you basically erase all elements from dictionary in the backtrack function and quite fast there will be no element left in dictionary. Probably you want to re-add the erased elements after the recursive call returns?

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜