I have a list of users with one or multiple attributes:
| Username | Attributes |
|---|---|
| Anna | A, B |
| Bob | A |
| Cesar | B |
| Daniel | C |
Now I must select a subgroup of three from the users so that that I get one user with attribut A and two with attribut B:
[A, B, B]
The solution is actually simple - I take Anna, Bob and Cesar.
But what is the algorithm to find the solution?
If I just start my search with the first entry in my requirement set (A) I would choose Anna because she has attribute A. Then I would find Bob for B - but then I wouldn't find anyone else for the second B :-( And I would return that it is not possible to find a solution.
So there must be a better logic to find the users - or to get output that it is just not possible to get such a list.
I guess this problem is well known for mathematicians - perhaps someone can just tell me a keyword describing my problem.
You can use a backtracking algorithm. The basic idea is to consider all possible combinations of users and attributes, starting with the first user in the list and checking if it satisfies the requirements. If it does, we move on to the next user and repeat the process, otherwise, we backtrack and try a different combination.