2019.03.05-算法-朋友分组问题

从业务上抽离出来的问题。

条件：

假设有一个已知的list:

list<string>  list= new arraylist<string>();

list.add("a");

list.add("b");

list.add("c");

list.add("d");

……

假设每一个字母代表一个人，人与人之间有两种关系：相容与互斥。通过isfriendly（a,b）可以获得两人之间的关系。

一个朋友圈中所有人都必须相容，且无法再加入其他成员。

例如list有4个人a、b、c、d， ab互斥  其他均相容 ，则可以得到两个朋友圈{acd}  {bcd}

——————

求：如何得到所有不同的朋友圈？

思路1：将所有人两两组合，形成两人朋友圈，接着两人朋友圈尝试添加其他人，形成3人朋友圈……直至所有朋友圈无法加人:，剔除掉重复朋友圈后得到所有不同的朋友圈。

（思路1光想想就脑壳痛……而且当所有人相容的时候显得很傻比= =）

 

思路2：先以a为核心，遍历所有人，找到所有与a相容的人，接而形成以a为中心辐射的朋友圈。   

             而第一个与a互斥的人，形成新的核心x……找到与该核心相容的人，形成以核心为辐射的新的朋友圈……

             第三个核心不能与a、x 兼容 ……

             当不再产生新的核心，代表所有朋友圈已经找到。

 其他思路暂时没想到，个人感觉思路2也不是很高效，欢迎有思路的大佬们指点。

——————————

思路2实现：未完待续……