如何在不重复相同组合的情况下配对列表中的元素？

Question

我有一个元素列表，我想对其进行分组（大小为 2、3、4 等）并在每次迭代中找到一些独特的组合。我有以下代码片段，它形成 group_size 大小的组合。

我想知道如何在新的迭代中避免重复组合。
对于group_size > 2，我也想避免members的任意两个元素重复。比方说：group_size = 3；然后 ['A', 'B', 'C'] 被接受，但是 ['A' 的任何其他组合， 'B',~] 或 ['B', 'C',~] 或 ['A', 'C',~]在未来的迭代中不被接受，其中'~'代表除['A', 'B'以外的任何元素， 'C'].

import random
from itertools import zip_longest
members = ['A', 'B', 'C', 'D', 'E', 'F', 'U', 'V', 'W', 'X', 'Y', 'Z']
group_size = 2
for i in range(10):
    random.shuffle(members)
    pairs_loc = [iter(members)] * group_size
    pairs = zip_longest(*pairs_loc)
    print(*pairs)

Answer 1

老实说，我不确定我是否正确理解了你想做什么，但让我试试看，也许它对你都有用。

对于第一点 Python 已经有了（我相信）您正在寻找的内容：itertools.combinations。

对于第二点，我们需要一些代码。一个注意事项：我相信您已经意识到，根据第二个要求，您会遇到一些情况，即并非所有成员都出现在至少一种组合中：例如，有 12 个成员和一个 groupsize > 6.

代码：

def select_combos(members, groupsize):
    assert groupsize > 1
    shuffle(members)
    if groupsize == 2:
        return list(combinations(members, 2))
    finalcombos = []
    usedcombos = []
    for c in combinations(members, groupsize):
        tempcombos = list(combinations(c, 2))
        for c2 in tempcombos:
            if c2 in usedcombos:
                break
        else:
            usedcombos += tempcombos
            finalcombos.append(c)
    return finalcombos

m = ['A', 'B', 'C', 'D', 'E', 'F', 'U', 'V', 'W', 'X', 'Y', 'Z']
select_combos(m, 2)
[('C', 'A'), ('C', 'Z'), ('C', 'Y'), ('C', 'E'), ('C', 'W'), ('C', 'B'), ('C', 'U'), ('C', 'X'), ('C', 'D'), ('C', 'V'), ('C', 'F'), ('A', 'Z'), ('A', 'Y'), ('A', 'E'), ('A', 'W'), ('A', 'B'), ('A', 'U'), ('A', 'X'), ('A', 'D'), ('A', 'V'), ('A', 'F'), ('Z', 'Y'), ('Z', 'E'), ('Z', 'W'), ('Z', 'B'), ('Z', 'U'), ('Z', 'X'), ('Z', 'D'), ('Z', 'V'), ('Z', 'F'), ('Y', 'E'), ('Y', 'W'), ('Y', 'B'), ('Y', 'U'), ('Y', 'X'), ('Y', 'D'), ('Y', 'V'), ('Y', 'F'), ('E', 'W'), ('E', 'B'), ('E', 'U'), ('E', 'X'), ('E', 'D'), ('E', 'V'), ('E', 'F'), ('W', 'B'), ('W', 'U'), ('W', 'X'), ('W', 'D'), ('W', 'V'), ('W', 'F'), ('B', 'U'), ('B', 'X'), ('B', 'D'), ('B', 'V'), ('B', 'F'), ('U', 'X'), ('U', 'D'), ('U', 'V'), ('U', 'F'), ('X', 'D'), ('X', 'V'), ('X', 'F'), ('D', 'V'), ('D', 'F'), ('V', 'F')]

select_combos(m, 5)
[('W', 'V', 'C', 'U', 'E'), ('W', 'A', 'X', 'B', 'F'), ('V', 'A', 'D', 'Y', 'Z')]

编辑现在清楚了，请求2人组就相当于安排了一场循环赛，所以我们可以用这里的standard circle method

旋转的一个快速而肮脏的实现：

def rotate(roster):
    half = (len(roster)+1)//2
    t=roster[1]
    roster[1] = roster[half]
    for j in range(half, len(roster)-1):
        roster[j] = roster[j+1]
    roster[-1] = roster[half-1]
    for j in range(half-1, 1, -1):
        roster[j] = roster[j-1]
    roster[2] = t

    for i in range(half):
        print(f'{roster[i]}-{roster[i+half]}   ', end = '')
    print()

members = ['A', 'B', 'C', 'D', 'E', 'F', 'U', 'V', 'W', 'X', 'Y', 'Z']
shuffle(members)
for r in range(len(members)):
    rotate(members)

在每次迭代中，这将轮换花名册一步并打印配对。请注意，在第 n 次迭代中，花名册以及配对将与开始时相同。

Answer 2

您可以使用集合字典来跟踪先前组中已经使用过的配对。然后 assemble 一个新组，该组基于您在每次添加到组中时限制的合格成员。请注意，可能会遇到死胡同，因此您的组形成逻辑需要能够自行重置并从不同的随机成员重新开始：

import random
members = ['A', 'B', 'C', 'D', 'E', 'F', 'U', 'V', 'W', 'X', 'Y', 'Z']

remaining  = {M:set(members)-{M} for M in members} # unused pairs by member
group_size = 3
for _ in range(10):
    more  = set()  # set of members that can be added to group
    group = []     # current group
    while len(group)<group_size:
        if len(more)+len(group)<group_size: # group not feasible
           more  = {m for m,r in remaining.items() if r} # reset
           group = [] 
        m = random.sample(more,1)[0] # select eligible member
        group.append(m)              # add to group 
        more &= remaining[m]         # constrain next members
    print(group)
    for m in group:                  # track unused pairs
        remaining[m].difference_update(group)   
        
['B', 'Z', 'Y']
['X', 'U', 'W']
['Y', 'U', 'C']
['D', 'Y', 'W']
['B', 'X', 'A']
['X', 'E', 'D']
['B', 'V', 'F']
['D', 'V', 'Z']
['E', 'A', 'F']
['A', 'C', 'Z']

如何在不重复相同组合的情况下配对列表中的元素？

How to Pair elements from a list without repeating the same combination?

python

combinations

itertools

shuffle