Generating a set of all combinations

Question

I am trying to solve 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.

The constraints are small, so I am using a brute force method of generating all the combinations of students, to calculate the maximum compatibility score:

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;
    }
};

The commented code does show different combinations being correctly generated. But the output that I get is 14 instead of 8. What am I doing wrong?

Answer 1

I guess you want to pair each student with a different mentor in each permutation. But thats not what you are doing here:

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

This two loops calculate the sum of all students paired with all mentors. In each iteraton of the outer loop this two for loops yield the same result, because the order of students does not matter.

I think you wanted this instead:

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

This will pair i-th student with i-th mentor. In the next iteration of the do loop there will be different pairings.