python beginner - построение списка пар с групповыми ограничениями

ProgramBox

python beginner — построение списка пар с групповыми ограничениями

Post author:admin
Запись опубликована:30 января, 2023
Post category:Вопросы по программированию

#python

Вопрос:

Для начала у меня есть этот список (предложенный в упражнении):

 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')]

В конце я должен написать randomMember(L) функцию с параметром 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

1. какая часть вашего кода является базовым кодом, который нельзя изменить? итак, я могу попробовать изменить следующую часть. Основываясь на текущем коде, я хочу знать, связана ли функция random (L) с Perm? Если нет, то как вы можете LCouples.append((L[k],L[Perm[k]])) повлиять на результат, который вы делаете в checkConstraint?

2. Кроме того, ваш пример, указанный для ('Tessa', 'G1'), ('Lewis', 'G1') , checkConstraint возвращает True , но возвращает False для ('Tessa', 'G1'), ('Joshua', 'G2') . Ваш код, вероятно, делает обратное.

3. @adamkwm вы можете редактировать LCouples.append((L[k],L[Пермь[k]])). Я отредактировал свой пример инструкции, это ошибка…

4. Разве это не может быть так же просто, как создание словаря с Gn where n is # 1,2,3,4,5 … как ключи и значения = список имен членов, которые соответствуют Gn? Затем делаем перестановку G1 с G2, G3, G4, G5 …. и повторяем через него.

5. Поскольку мы выполняем случайное сопряжение, может ли один участник быть сопряжен с двумя людьми? Существуют ли дополнительные ограничения, при которых член не может быть соединен с кем-либо еще в окончательном списке?

Ответ №1:

Я не знаю, нужна ли ваша перестановка ()? Я нахожу способ, не используя его.

 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 в вашем randomMember(L) , который передан checkConstrainst(Perm,random(L)) , не имеет никакого отношения к D in 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 пар вместо 7 пар на 14 человек. Некоторые из них являются дубликатами, такими как (('Tessa', 'G1'), ('Tom', 'G3')) and (('Tom', 'G3'), ('Tessa', 'G1')) , остальные будут представлять собой одно-два отношения, подобные (('Evan', 'G2'), ('Maddie', 'G1')) and (('Lewis', 'G1'), ('Evan', 'G2')) .

1. Спасибо за ваш ответ… Но я должен использовать Пермь в checkConstraint… К сожалению…

2. Я отредактировал исходное сообщение, в том числе random(L) .

3. И включил то, что random_member(L) должно выглядеть (я должен завершить).

4. @GeneralHarrigton но в вашем базовом коде нет checkConstraint() .

5. Я должен использовать его в то время как randomMember(L)

Ответ №2:

Вот как вы можете использовать combinations метод для получения списка всех возможных групп из 2, где члены группы из 2 не принадлежат к одной группе:

 from itertools import combinations

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')]

random = []
for a, b in combinations(Members, 2):
    if a[1] != b[1]:
        random.append((a, b))

print(random)

Вывод:

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

Ответ №3:

Для меня это выглядит так, как в этой строке

     while checkConstrainst(Perm,random(L)) == False:

у вас не должно быть random(L) просто L . Вы уже рандомизируете свои перестановки

Если вам нужно сделать ‘L’ случайным, либо сделайте это сразу после ввода функции:

 def randomMember(L):
    L = random(L)
    n = len(L)

или вообще не иметь его и вызывать функцию с рандомизированным L:

 ...
randomMember(random(L))

Обоснование заключается в том, что в вашей исходной функции вы проверяете перестановки по рандомизированному L , но затем объединяете пары из оригинала L

Ответ №4:

Вот способ сделать это. Я прокомментировал, чтобы дать объяснение того, что я делаю в программе.

 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 randomMember(L):
    LCouples = []

    for memb1 in Members: #iterate thru each member of Members list

        #now create a list of all members that do not belong to same Group as memb1
        memb_others = [j for j in Members if j[1] != memb1[1]]

        #generate a random number between 0 and length of the new list of members
        r = random.randint(0,len(memb_others)-1)

        #pair them as couples and append to LCouples
        #the pairing will ensure no couple from same group are paired
        LCouples.append((memb1,memb_others[r]))

    #return the list of all randomly paired couples
    return LCouples

#print the full list of random members
print (randomMember(Members))

Несколько запусков этого сгенерировали следующие результаты:

Выполнить 1:

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

Выполнить 2:

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

Выполнить 3:

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