创建授予特权用户所需的最低组

Question

问题

有多个用户需要特权来执行特定任务。 不得授予用户比所需的更多特权。两个或多个组可以包含一些共同特权。

例如，

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

我们需要创建具有特权的最少组，以便我们可以将用户分配给该组。

例如，

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

---

---

某些测试用例

案例1：

输入：

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

输出：

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

---

案例2：

输入：

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

输出：

解决方案1解决

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

方案2：

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

---

Answer 1

假设

• 可以将用户分配给多个组
• 特权可以分配给多个组
• 用户，则不能分配给具有不需要特权的组的组

，

- 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

请注意，这将使您拥有一个包含所有特权的组。如果没有分配给它的用户，则可以将其分配给假设的管理用户或丢弃。

Answer 2

关于Ravenspoint的算法。说，

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

从我看到的算法中，我们拥有贪婪的算法首先形成了该组（P1，P2，P3）。这意味着三组变得有必要：

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

它仅用两组就错过了该解决方案：

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

我怀疑OP的问题是设定盖问题的变化，可能是NP库件。如果是这样，大数据集将需要近似算法，但可能并不总是达到最佳解决方案。