我正在尝试创建一种算法,它可以从偶数个n个人中创建唯一的配对。之后,应将这些对划分为n-1天。所以每天,每个人都会遇到其他人。配对不应该重复。算法每次运行时都应提供不同的解决方案
例如。 我的起始数组是[1,2,3,4]-它被转换成以下对:
[1,2],[1,3],[1,4],
[2,3],[2,4],
[3,4]
现在这些对需要像这样在n-1天内分开
day 1 [1,2] & [3,4]
day 2 [1,3] & [2,4]
day 3 [1,4] & [2,3]
谢谢你的帮助
更新
多亏了这些答案,我才写出了这个解决方案
fun createDates(userIds: List<Int>): List<DateEntity> {
val dates = ArrayList<DateEntity>()
val userCount = userIds.size
val days = userCount - 1
val half = userCount / 2
val mutableUsers = userIds.toMutableList()
for (day in 0 until days) {
val firstHalf = mutableUsers.slice(0 until half)
val secondHalf = mutableUsers.slice(half until userCount).reversed()
for (i in firstHalf.indices) {
dates.add(DateEntity(day, firstHalf[i], secondHalf[i]))
}
// rotating the array
mutableUsers.add(1, mutableUsers.removeLast())
}
return dates
}
循环算法:
把人分成两排
每天,第一排的人与下一排的人配对。 如果人数为奇数,则一人等待一天
白班结束后,除第一人外,所有人以循环方式:
等等
这段代码只执行MBo描述的the algorithm
cycle
只循环数组n
个位置,因此,例如,cycle (2, ['a', 'b', 'c', 'd', 'e'])
产生['c', 'd', 'e', 'a', 'b']
pairs
将数组两端的两个元素成对放置,然后将它们旁边的两个元素成对放置,以此类推pairs (['a', 'b', 'c', 'd', 'e', 'f'])
产生[['a', 'f'], ['b', 'e'], ['c', 'd']]
我们在
roundRobin
中组合这些值,对于每一天,我们移除第一个值,循环剩余的值,将第一个值放回,并将列表变成成对如果您想要额外的随机性,我建议您在开始之前简单地洗牌数组
如果您希望允许奇数个参与者,每次都有一个坐在外面,我会添加一个专门的坐在外面的参与者,然后每天与不同的参与者配对