给一个list of person，每个person有一个groupid。要求随机两两pair，同组的不能被pair到一起。最近频率很高的yelp题。大家有什么想法吗？
这题其实领英和snap也考，我知道大概做法
应该怎么做呢
我回头写一下吧，欢迎大家先讨论
说下另外两家公司考的形式
圣诞节送礼物，礼物random送给别人，但不能送给自己，输出送礼物的方案
希望有人能来踊跃讨论下
本质就是random选某个人pair，如果是同一个group就无效，那么retry。那么这样有可能出现无效的概率就越来越高。这相当于brutal force。然后最关键的trick是如何不出现无效的选择。这就是考察点。我先不说答案了，大家讨论。谷歌其实有一道类似的random扫雷游戏的题目。给一个二维矩阵，随机不断产生地雷，地雷不能出现在已经出现过的位置。
扫雷那个是个特别明显的reservoir sampling。如果是往reservoir sampling想的话，那我觉得就是每次随机选一个之后，第二个用reservoir sampling。但是每次都得把整个list扫一遍。感觉这样复杂度太高了
不对，这不是最优解
我也觉得是，复杂度太高了
所以x老师正确的解法是什么呢
可不可以以groupid为key 然后list of 同组的所有person为value 建立一个dictionary (in python) 然后就依次从俩不同的groupid里各取一个组成pair 这样？初步是这样想 欢迎指正和讨论
注意我说的这三道题本质是一样的，而且关键点是 random 但不能重复选
如果先选组，再选人的话。不能保证在不同组的每个人被抽取的概率是一样的吧
先把list随机排列，然后前一个人送给下一个人。
可以吗？
我觉得可行啊！
同一个group的问题如何解决？
如果是同一个group的就找下一个
pair 是不是从这个 list 里删除呢？
其实还不是最优解，有效率更高的解法，不会选择到同一个group的人