Create minimum groups required to grant privileges users-CodePudding

Problem

There are multiple users who require privileges to perform a certain task. A user must not be granted more privileges than needed. Two or more groups can contain some common privileges.

e.g.

user1 -> p1 p2 p3
user2 -> p1    p3
user3 ->    p2

We need to create a minimum number of groups with privileges so that we can assign users to that group.

e.g.

group1 (p1 p3) -> user1, user2
group2  (p2)   -> user1, user3

Some test cases

case 1:

Input:

user1 -> p1
user2 ->    p2
user3 ->        p3
user3 ->           p4

Output:

group1(p1) -> user1
group2(p2) -> user2
group3(p3) -> user3
group4(p4) -> user4

case 2 :

Input:

user1 ->     p2  p3  p4
user2 ->     p2  p3  p4
user3 -> p1  p2  p3
user4 ->     p2  p3

Output:

solution1

group1(p1) -> user3
group2(p2,p3) -> user1,user2,user3,user4
group3(p4) -> user1, user2

solution2:

group1(p1) -> user3
group2(p2,p3,p4) -> user1,user2
group3(p2,p3) -> user3, user4

CodePudding user response：

Assuming

Users can be assigned to multiple groups
Privileges can be assigned to multiple groups
User can NOT be assigned to groups with unneeded privileges

Then

- Assign all privileges to one group
- Sort users into order of increasing number of privileges needed
- Loop over users 
  - Loop over groups
     - IF group contains user's unmet privileges
         - IF group contains no extra privileges
             - Assign user to group
  - ENDGROUPLOOP
  - If user's needs are NOT all met
     - Add new group with unmet privileges
     - Assign user to new group
  - ENDIF
- ENDUSERLOOP

Note that this will leave you with one group that contains every privilege. If this has no user assigned to it, then you can assign this to an assumed ADMIN user, or discard it.

CodePudding user response：

Regarding ravenspoint's algorithm. Say we have,

user1 -> p1 p2 p3
user2 -> p1    p3
user3 ->    p2

From what I can see, the algorithm greedily first forms the group (p1, p2, p3). It means three groups become necessary:

group1(p1, p2, p3) -> user1
group2(p1, p3) -> user2
group3(p2) -> user3

It misses out on this solution with just two groups:

group1(p1, p3) -> user1, user2
group2(p2) -> user1, user3

I suspect the OP's problem is a variation of the Set Cover Problem and possibly NP-complete. If so, an approximate algorithm becomes necessary for big data sets but may not always reach an optimal solution.