python 初学者 - 构建具有组约束的情侣列表

Question

首先，我有这个列表(在练习中建议):

Members = [('Tessa','G1'),('Evan','G2'),('Tom','G3'),
('Mia','G3'),('Claire','G3'),('Billie','G4'),('Adrian',
'G2'),('Maddie','G1'),('Lewis','G1'),('Tony','G2'),('Joyce',
'G1'),('Julian','G5'),('Joshua','G2')('Warren','G3')]

最后，我必须编写一个带有参数 L 的 randomMember(L) 函数，它是上面定义的列表 Members 两人一组，具有以下约束:

同一组(G1, G2, ...)的两个成员不能见面。

例如，使用列表 Members，"Tessa" 和 "Lewis" 不能互相相遇。

所以，我已经写了这个(已经提供了基本代码，所以循环的位置应该不会改变)

def randomMember(L):
    n = len(L)
    Perm = permutation(n)
    while checkConstrainst(Perm,random(L)) == False:
        Perm = permutation(n)
    LCouples=[]
    for k in range (n):
        LCouples.append((L[k],L[Perm[k]]))
    return LCouples

为了进一步解释，checkConstrainst 函数有两个参数。 Perm，它是一个整数列表，L 是一个列表，表示之前在 Members 列表中进行的抽签。

这个函数的目的是保证2个人不属于同一个组。输入 L 看起来像:[(('Tessa', 'G1'), ('Lewis', 'G1')), (('Joshua', 'G2'), ('Billie', 'G4'))]

def checkConstrainst(Perm,L):

    for i in range(len(Perm)):
        PeopleGroup_1, PeopleGroup_2 = L[i] 
        People1, Group1 = PeopleGroup_1
        People2, Group2 = PeopleGroup_2
        
        if Group1 == Group2:
            return False
    return True

我必须使用排列来使它工作...我不知道如何使用输入的列表来确保 Perm 目前验证约束。

对于列表 [(('Tessa', 'G1'), ('Lewis', 'G1')), (('Joshua', 'G2'), ('Billie', ' G4'))]，checkConstraint 返回 False 并且对于列表 [(('Tessa', 'G1'), ('Joshua' , 'G2')), (('Billie', 'G4'), ('Lewis', 'G1'))] 返回 True 因为每对夫妇都不是来自同一对组。

permutation 函数就是用来生成随机整数的。

如果你需要，这里是代码:

def permutation(n):
    L=[]
    Perm=[]
    j=0
    for i in range(n):
        L.append(i)
    for k in range(n):
        alea = rd.randint(0,len(L)-1)
        j=L.pop(alea)
        Perm.append(j)
    return Perm

在 RandomMember 中，您还有一个 Random 函数，它将 Members 列表作为参数。此函数使几个人无需检查他们是否来自同一组(这是 RandomMember 的目标)。 Random 返回如下内容:[(('Tessa', 'G1'), ('Lewis', 'G1')), (('Joshua', 'G2'), ('Billie', 'G4'))].

所以，我的问题是我已经测试了 checkConstrainst，它运行良好。但是，在 randomMember 函数中，在构建 LCouples 列表时，一对夫妇中有 2 个人属于同一组......

这里如果你需要的是random, derangement 和isDerangement 函数:

def isDerangement(Perm):
    for i in range(len(Perm)):
        if Perm[i]==i:
            return False
    return True

def derangement(n):
    Perm=permutation(n)
    while isDerangement(Perm)==False:
        Perm=permutation(n)
    return Perm

def random(L):
    n=len(L)
    Couples=[]
    D=derangement(n)

    for k in range(n):
        Couples.append((L[k],L[D[k]]))
    return Couples

尽管看了几个小时，我还是不明白我的错误在哪里......

对于randomMember(L)，这是我应该完成的基本代码:

def randomMember(L):
    .............................................
    Perm =........................................
    while ......................................:
        Perm =....................................
    LCouples =[]
    for k in range (n):
    LCouples . append (.......................).
    return LCouples

Answer 1

我不知道你的 permutation() 是否有必要？我找到了一种不用它的方法。

import random
members = [
    ('Tessa','G1'),('Evan','G2'),('Tom','G3'),('Mia','G3'),('Claire','G3'),
    ('Billie','G4'), ('Adrian','G2'),('Maddie','G1'),('Lewis','G1'),
    ('Tony','G2'),('Joyce','G1'),('Julian','G5'),('Joshua','G2'),('Warren','G3')
]

# I don't know how your random(L) look like but this function should do the same
def random_couples(L):
    couples = []
    # shuffle the members
    rm = random.sample(L,len(L))
    for i in range(0, len(L), 2):
        couples.append((rm[i], rm[i+1]))
    # return couples of random members
    return couples

# no Perm needed
def check_constraint(L):
    for pg1, pg2 in L:
        if pg1[1] == pg2[1]:
            return False
    return True

def random_member(L):
    Lcouples = random_couples(L)
    while check_constraint(Lcouples) == False:
        Lcouples = random_couples(L)
    return Lcouples

print(random_member(members))

输出:

[(('Warren', 'G3'), ('Lewis', 'G1')), (('Maddie', 'G1'), ('Adrian', 'G2')), 
(('Evan', 'G2'), ('Tessa', 'G1')), (('Claire', 'G3'), ('Julian', 'G5')), 
(('Mia', 'G3'), ('Tony', 'G2')), (('Tom', 'G3'), ('Joyce', 'G1')), 
(('Joshua', 'G2'), ('Billie', 'G4'))]

[(('Warren', 'G3'), ('Joshua', 'G2')), (('Tony', 'G2'), ('Mia', 'G3')),
(('Billie', 'G4'), ('Tom', 'G3')), (('Claire', 'G3'), ('Lewis', 'G1')), 
(('Evan', 'G2'), ('Maddie', 'G1')), (('Tessa', 'G1'), ('Adrian', 'G2')), 
(('Joyce', 'G1'), ('Julian', 'G5'))]

[(('Lewis', 'G1'), ('Warren', 'G3')), (('Tony', 'G2'), ('Joyce', 'G1')), 
(('Adrian', 'G2'), ('Tom', 'G3')), (('Joshua', 'G2'), ('Tessa', 'G1')), 
(('Billie', 'G4'), ('Evan', 'G2')), (('Julian', 'G5'), ('Mia', 'G3')), 
(('Maddie', 'G1'), ('Claire', 'G3'))]

---

对于 Perm 要求

我现在可能知道该怎么做了，但我想先说说为什么你的代码不起作用。

传递给 checkConstrainst(Perm,random(L)) 的 randomMember(L) 中的

Perm 与 无关D 在 random(L) 中。您生成两个不同的数字列表，使用 D 创建随机对并对其进行验证，然后使用 Perm 返回未验证的最终结果。

关键是使用 Perm 来创建随机对。

import random

members = [
    ('Tessa','G1'),('Evan','G2'),('Tom','G3'),('Mia','G3'),('Claire','G3'),
    ('Billie','G4'), ('Adrian','G2'),('Maddie','G1'),('Lewis','G1'),
    ('Tony','G2'),('Joyce','G1'),('Julian','G5'),('Joshua','G2'),('Warren','G3')
]

def check_constraint(perm,L):
    n = len(L)
    # use perm passed in to create random couples
    couples = [(L[i], L[perm[i]]) for i in range(n)]
    # check if they are in same group
    for pg1, pg2 in couples:
        if pg1[1] == pg2[1]:
            return False
    return True

def random_members(L):
    n = len(L)
    # create a list of size n with shuffled numbers equal to your permutation(n)
    perm = random.sample(range(n),n)
    # move random selection inside check_constraint() so just pass L here
    while check_constraint(perm,L) == False:
        perm = random.sample(range(n),n)
    couples = [(L[i], L[perm[i]]) for i in range(n)]
    return couples

print(random_members(members))

输出:

[(('Tessa', 'G1'), ('Tom', 'G3')), (('Evan', 'G2'), ('Maddie', 'G1')),
(('Tom', 'G3'), ('Tessa', 'G1')), (('Mia', 'G3'), ('Adrian', 'G2')),
(('Claire', 'G3'), ('Julian', 'G5')), (('Billie', 'G4'), ('Mia', 'G3')),
(('Adrian', 'G2'), ('Warren', 'G3')), (('Maddie', 'G1'), ('Joshua', 'G2')),
(('Lewis', 'G1'), ('Evan', 'G2')), (('Tony', 'G2'), ('Billie', 'G4')),
(('Joyce', 'G1'), ('Claire', 'G3')), (('Julian', 'G5'), ('Tony', 'G2')),
(('Joshua', 'G2'), ('Lewis', 'G1')), (('Warren', 'G3'), ('Joyce', 'G1'))]

如果这是您的预期结果，我感到很奇怪。我们将有 14 对夫妇，而不是 14 人的 7 对夫妇。其中一些是重复的，例如 (('Tessa', 'G1'), ('Tom', 'G3')) 和 (('Tom', 'G3'), ( 'Tessa', 'G1'))，剩下的就是一对二的关系，比如 (('Evan', 'G2'), ('Maddie', 'G1')) 和 (('Lewis', 'G1'), ('Evan', 'G2'))。