生成一组所有组合

Question

我正在尝试解决a problem:

There is a survey that consists of n questions where each question's answer is either 0 (no) or 1 (yes). The answers of the students are represented by a 2D integer array students where students[i] is an integer array that contains the answers of the ith student (0-indexed) (similarly for mentors as well).
Each student will be assigned to one mentor, and each mentor will have one student assigned to them. The compatibility score of a student-mentor pair is the number of answers that are the same for both the student and the mentor.
For e.g.: if students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]] then output should be 8. (student 0 paired with mentor 2 (score 3), student 1 paired with mentor 0 (score 2) and student 2 paired with mentor 1 (score 3). Total compatibility: 8.

约束很小，所以我使用暴力生成所有学生组合的方法来计算最大兼容性分数：

class Solution {
public:
    int check(vector<int>& s, vector<int>& m) {
        // calculates and returns max compatibility score
        int res=0;
        
        for(int i=0; i<s.size(); i++)
            if(s[i]==m[i]) res++;
        
        return res;
    }

    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
        int res=0;
        
        sort(students.begin(), students.end());
        do {
            int curr=0;
            // for(auto s: students) {
            //     for(auto val: s) {
            //         cout<<val<<" ";
            //     }
            //     cout<<"\n";
            // }

            for(auto s: students) {
                for(auto m: mentors) {
                    curr+=check(s, m);
                }
            }
            res=max(res, curr);
        } while(next_permutation(students.begin(), students.end()));
        
        return res;
    }
};

注释代码确实显示了正确生成的不同组合。但是我得到的输出是 14 而不是 8。我做错了什么？

Answer 1

我猜您想在每个排列中将每个学生与不同的导师配对。但这不是你在这里做的：

        for(auto s: students) {
            for(auto m: mentors) {
                curr+=check(s, m);
            }
        }

这两个循环计算所有学生与所有导师配对的总和。在外部循环的每次迭代中，这两个 for 循环产生相同的结果，因为 students 的顺序无关紧要。

我想你想要这个：

  for (size_t i = 0; i < std::min(students.size(),mentors.size()); ++i) {
       curr += check( students[i], mentor[i]);
  }

这会将第 i 个学生与第 i 个导师配对。在 do 循环的下一次迭代中，将有不同的配对。

生成一组所有组合

Generating a set of all combinations

c++

algorithm

permutation