在 n-1 天内以独特的对分配 n 个人的算法

Question

我正在尝试创建一种算法，该算法可以从偶数 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
    }

Answer 1

循环算法：

把人排成两排。

每天顶行的人都会与下排的相应人配对。如果人数是奇数，一个人等一天。

day 1
A B C
D E F
A:D B:E C:F

白班后除第一人以外的所有循环方式：

day 2
A D B
E F C
A:E D:F B:C 

day 3
A E D
F C B
A:F E:C D:B

等等。

Answer 2

此代码仅执行 MBo 描述的。

const cycle = (n, xs) => 
  [... xs .slice (n % xs .length), ... xs .slice (0, n % xs .length)]

const pairs = (xs) =>
  xs.length < 2 ? [] : [[xs [0], xs [xs .length - 1]], ...pairs (xs .slice (1, -1))]

const roundRobin = ([x, ...xs]) => 
  Array.from(xs, (_, i) => pairs ([x, ...cycle(i, xs)]))

console .log (roundRobin ([1, 2, 3, 4, 5, 6])) //=>
// (1 - 6)  &  (2 - 5)  &  (3 - 4)
// (1 - 2)  &  (3 - 6)  &  (4 - 5)
// (1 - 3)  &  (4 - 2)  &  (5 - 6)
// (1 - 4)  &  (5 - 3)  &  (6 - 2)
// (1 - 5)  &  (6 - 4)  &  (2 - 3)

.as-console-wrapper {max-height: 100% !important; top: 0}

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 中组合这些，对于每一天，我们删除第一个值，循环剩余的值，将第一个值放回原处，并将列表成对。

如果您想要额外的随机性，我建议您在开始之前简单地洗牌。

如果你想允许奇数的参与者，每次一个人坐在外面，我会添加一个专门的坐在外面的参与者，然后每天与不同的参与者配对。

在 n-1 天内以独特的对分配 n 个人的算法

Algorithm to distribute n people in unique pairs over n-1 days

python

java

algorithm

logic

kotlin