对元组列表进行排序，但不希望按键分组

Question

我有一个ID列表，代表用户。我正在编写一个函数，将这个ID列表转换成用户配对的日程表（pairings），如下:

ids = [1, 2, 3, 4]

这个涉及到的时间表会是这样的：

week 1: (1, 2), (3, 4)
week 2: (1, 3), (2, 4)
week 3: (1, 4), (2, 3)
week 4: (1, 2), (3, 4) [repeat of week 1]

等等，我正在尝试使用嵌套的for循环来处理用户ID数量和由此产生的组合。

ids = [1,2,3,4]
matchups = []

#generate all the combinations of matchups
for subset in itertools.combinations(ids,2):
    matchups.append(subset)

这会返回所有可能的配对结果，以元组列表的形式呈现 - 很好！这是我要寻找的核心。现在的问题是如何将其转换为可用的东西。例如，上面的代码针对matchups返回以下列表:

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

我试图使用一个复杂的递归函数来构建每周唯一配对的列表，然后我意识到如果我按正确顺序列出上述列表，我可以简单地使用它从头到尾分配配对，而不管周次，并在到达结尾时重复。也就是说，我可以使用已知每周所需配对数量和已知周数来分配配对到周次。

为此，我一直在尝试找出如何根据元素不相等的方式对元组列表进行排序。sorted()方法有很多对这种情况有用的实现，但我只能得到像上面的结果那样分组的类似结果。

我希望找到sorted()的一个用法，它将返回以下内容，几乎像一种反向排序：

[(1, 2), (3, 4), (1, 3), (2, 4), (1, 4), (2, 3)]

有没有办法用lambda实现这个？

编辑：我刚才意识到第一个元素需要与第六个元素配对，第二个与第五个，第三个与第四个。我不知道这是否推广到一般情况，但我认为可能是可能的，因为我已经采取了其他措施以确保始终有偶数个ID。

现在，我确定有一种方法可以插值列表以实现这一点。

编辑2：看起来之前的直觉是错误的 - 它不适用于6个ID，很可能任何超过6个ID的情况都会失败。我回来尝试找出一种基于密钥分散而不是排序的方法。

- dkhaupt

---

random.shuffle 是一种反排序的方法 :) - pp_

非常正确- 我意识到我的术语不太好- 更确切地说，我需要确保唯一性而不是按键分组。 - dkhaupt

为什么不能使用for循环？第二个列表的顺序只是0 5 1 4 2 3。 - pp_

@pp_ 但是这个推论如何适用于超过4个元素的情况呢？ - Garrett R

当你说你必须配对第1-6、第2-5和第3-4时，我不清楚你的意思。这些成对的属性是什么？例如，第1-6对使用2两次和4根本不使用。 - Prune

Answer 1

我相信你正在寻找的是经典的轮流调度算法。

请将所有玩家按照您方便的任何顺序分成两行：

1 2 3 4
5 6 7 8 

你的第一轮配对是1-5、2-6、3-7、4-8。 在接下来的几周中，旋转除了#1位置以外的所有位置：上排向左移动，下排向右移动；落到末尾的人（2和8）会向上/下移动到空位。

1 3 4 8
2 5 6 7 

如果您还需要平衡家庭和外出搭配，那么在完成这个循环之后，请返回并在每两周中交换行。

- Prune

---

我很感谢你的回答，但是轮询算法相比于我帖子中的组合有什么优势吗？它们是否不同？虽然我只有4个ID，但我认为最终结果可能是相同的。无论如何，我对combination()方法生成的元组输出感到满意，我想这更多是一个排序/列表操作的问题。 - dkhaupt

循环轮换配对很容易推广到任意数量的ID，并保证每个ID在每组N/2个配对中都有一个配对。根据您的描述，我认为这就是您的“反排序”的目的所在。 - Prune

我认为是这样的，但同时我相信combination()方法的输出也可以给我轮流赛制的效果。有没有实现轮流赛制的包？ - dkhaupt

Answer 2

潜在的非惯用解决方案，但它有效。也许有人可以使它更具Python风格？ :D

def antisort(x):
    if len(x) > 0:
        return [x[0]] + antisort(x[-1:0:-1])
    else:
        return []

>>> antisort([(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)])
[(1, 2), (3, 4), (1, 3), (2, 4), (1, 4), (2, 3)]

这个切片符号只取第一个元素之后的所有内容并将其反转：

x[-1:0:-1]

- Dmiters

---

谢谢你的回答-看起来我在编辑中的直觉是错误的，因为这适用于4个元素但不适用于6个。 - dkhaupt

Answer 3

这是我在评论中所指的内容：

a = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
new = []

i, j = len(a)-1, 0

for n in range(i+1):
    if n % 2:
        new.append(a[i])
        i -= 1
    else:
        new.append(a[j])
        j += 1

print(new)

输出：

[(1, 2), (3, 4), (1, 3), (2, 4), (1, 4), (2, 3)]

- pp_

---

这个可以处理4个元素，但是不能处理更多——看来我修改时的直觉是错误的。不过还是谢谢。 - dkhaupt

@dkhaupt 为什么是4？列表有6个元素。您是指星期吗？ - pp_

是的-元组输出有6个元素，抱歉-我指的是生成元组输出的ID列表。使用4个ID可以工作，但当我增加到6个ID时，它就不再工作了。 - dkhaupt

Answer 4

这是维基百科轮流比赛算法的实现。

x = range(1, 11) #10 players

def round_robin(someIds):
    someIds = someIds[::2] + someIds[1::2]
    first, someIds = [someIds[0]], someIds[1:]
    n = len(someIds)
    for i in range(n):
        top = someIds[:n/2]
        bottom = someIds[n/2:]
        yield zip(first+top, bottom)
        someIds = someIds[-1:] + someIds[:-1]


for thing in round_robin(x):
    print thing

输出

[(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)]
[(1, 3), (4, 5), (6, 7), (8, 9), (10, 2)]
[(1, 4), (5, 6), (7, 8), (9, 10), (2, 3)]
[(1, 5), (6, 7), (8, 9), (10, 2), (3, 4)]
[(1, 6), (7, 8), (9, 10), (2, 3), (4, 5)]
[(1, 7), (8, 9), (10, 2), (3, 4), (5, 6)]
[(1, 8), (9, 10), (2, 3), (4, 5), (6, 7)]
[(1, 9), (10, 2), (3, 4), (5, 6), (7, 8)]
[(1, 10), (2, 3), (4, 5), (6, 7), (8, 9)]

- Garrett R

---

这个可行，谢谢。你和@Prune是对的 - 我一开始就应该研究一下这个。 - dkhaupt

将其更改为按照您要求的顺序打印。 - Garrett R

再次感谢-我正在使用pythonfiddle.com进行工作，但是当我尝试在我的家庭环境（Python 3.4）中运行它时，我会收到以下错误：TypeError：slice indices must be integers or None or have an __index__method。有任何想法为什么会这样吗？ - dkhaupt

我认为Python3在整数除法时使用//，而不是单个/表示浮点运算。 - Garrett R

非常感谢 - 我发现那个fiddle网站可能是在2.x版本上运行的，但我不知道Python3有一个不同的整数除法运算符。 - dkhaupt