从Python中长度为n的列表中获取n*k个唯一的2集合

人气:730 发布:2022-10-16 标签: python list algorithm set

问题描述

我有以下的Python智囊团:我们安排了一个为期30天的计划,有48名参与者。在这个项目中,每一天的参与者都是成对的。参与者不能有两次相同的合作伙伴,所有参与者都必须每天配对。附言:我希望我的数学题是对的。

我已经完成了一个实现,但感觉非常笨重。有没有一种有效的方法来做到这一点?也许是在使用笛卡尔的乘积?非常感谢所有反馈和提示。

# list of people: 48
# list of days: 30
# each day, the people need to be split into pairs of two.
# the same pair cannot occur twice

import random
from collections import Counter

class person ():

    def __init__ (self, id):
        self.id = id


class schedule ():

    def __init__ (self, days):
        self.people_list = []
        self.days = days
        self.placed_people = []
        self.sets = []


    def create_people_list(self, rangex):

        for id in range(rangex): 
            new_person = person(id)
            self.people_list.append(new_person) 

        print(f"{len(self.people_list)} people and {self.days} days will be considered.")


    def assign_pairs(self):


        for day in range(self.days): # for each of the 30 days..
 
            print("-" * 80)
            print(f"DAY {day + 1}") 

            self.placed_people = [] # we set a new list to contain ids of placed people

            
            while Counter([pers.id for pers in self.people_list]) != Counter(self.placed_people):

                pool = list( set([pers.id for pers in self.people_list]) - set(self.placed_people))
                # print(pool)

                person_id = random.choice(pool) # pick random person
                person2_id = random.choice(pool) # pick random person

                    
                if person_id == person2_id: continue 

                if not set([person_id, person2_id]) in self.sets or len(pool) == 2:
                    
                    if len(pool) == 2: person_id, person2_id = pool[0], pool[1]

                    self.sets.append(set([person_id, person2_id]) )
                    self.placed_people.append(person_id)
                    self.placed_people.append(person2_id)

                    print(f"{person_id} {person2_id}, ", end="")

schdl = schedule(30) # initiate schedule with 30 days
schdl.create_people_list(48)
schdl.assign_pairs()

输出:

48 people and 30 days will be considered.

--------------------------------------------------------------------------------
DAY 1
37 40, 34 4, 1 46, 13 39, 12 35, 18 33, 25 24, 23 31, 17 42, 32 19, 36 0, 11 9, 7 45, 10 21, 44 43, 29 41, 38 16, 15 22, 2 20, 26 47, 30 28, 3 8, 6 27, 5 14,

--------------------------------------------------------------------------------
DAY 2
42 28, 25 15, 6 17, 2 14, 7 40, 11 4, 22 37, 33 20, 0 16, 3 39, 19 47, 46 24, 12 27, 26 1, 34 10, 45 8, 23 13, 32 41, 9 29, 44 31, 30 5, 38 18, 43 21, 35 36,

--------------------------------------------------------------------------------
DAY 3
8 28, 33 12, 40 26, 5 35, 13 31, 29 43, 44 21, 11 30, 1 7, 34 2, 47 45, 46 17, 4 23, 32 15, 14 22, 36 42, 16 41, 37 19, 38 3, 20 6, 10 0, 24 9, 27 25, 18 39,

--------------------------------------------------------------------------------

[...]

--------------------------------------------------------------------------------
DAY 29
4 18, 38 28, 24 22, 23 33, 9 41, 40 20, 26 39, 2 42, 15 10, 12 21, 11 45, 46 7, 35 27, 29 36, 3 31, 19 6, 47 32, 25 43, 13 44, 1 37, 14 0, 16 17, 30 34, 8 5,

--------------------------------------------------------------------------------
DAY 30
17 31, 25 7, 6 10, 35 9, 41 4, 16 40, 47 43, 39 36, 19 44, 23 11, 13 29, 21 46, 32 34, 12 5, 26 14, 15 0, 28 24, 2 37, 8 22, 27 38, 45 18, 3 20, 1 33, 42 30,

感谢您的宝贵时间!另外,还有一个后续问题:我如何计算是否有可能解决任务,即每天将所有参与者安排成唯一的一对?

推荐答案

现实生活中的循环赛

Round-robin tournaments非常容易组织。事实上,算法非常简单,只需给人类简单的指令,你就可以在没有任何纸张或计算机的情况下组织一场人类之间的循环赛。

您有偶数个N = 48人可以配对。假设您有一张长桌,一边有N // 2个座位,另一边面对N // 2个座位。请所有人在那张桌子上就座。

这是您的第一个配对。

呼叫其中一个座位1&q;。

移动到下一个配对:坐在1号座位上的人没有移动。其他人绕着桌子顺时针移动一个座位。

Current pairing
1 2 3 4
8 7 6 5

Next pairing
1 8 2 3
7 6 5 4

在Python中的循环赛

# a table is a simple list of humans
def next_table(table):
  return [table[0]] + [table[-1]] + table[1:-1]
  # [0 1 2 3 4 5 6 7] -> [0 7 1 2 3 4 5 6]

# a pairing is a list of pairs of humans
def pairing_from_table(table):
  return list(zip(table[:len(table)//2], table[-1:len(table)//2-1:-1]))
  # [0 1 2 3 4 5 6 7] -> [(0,7), (1,6), (2,5), (3,4)]

# a human is an int
def get_programme(programme_length, number_participants):
  table = list(range(number_participants))
  pairing_list = []
  for day in range(programme_length):
    pairing_list.append(pairing_from_table(table))
    table = next_table(table)
  return pairing_list

print(get_programme(3, 8))
# [[(0, 7), (1, 6), (2, 5), (3, 4)],
#  [(0, 6), (7, 5), (1, 4), (2, 3)],
#  [(0, 5), (6, 4), (7, 3), (1, 2)]]


print(get_programme(30, 48))

如果您希望人类是自定义对象而不是int,可以将第二个参数number_participants直接替换为列表table;然后用户可以提供他们想要的列表:

def get_programme(programme_length, table):
  pairing_list = []
  for day in range(programme_length):
    pairing_list.append(pairing_from_table(table))
    table = next_table(table)
  return pairing_list

print(get_programme(3, ['Alice', 'Boubakar', 'Chen', 'Damian']))
# [[('Alice', 'Damian'), ('Boubakar', 'Chen')],
#  [('Alice', 'Chen'), ('Damian', 'Boubakar')],
#  [('Alice', 'Boubakar'), ('Chen', 'Damian')]]

后续问题:什么时候有解决方案?

如果有N人,则每个人可以与N-1不同的人配对。如果N为偶数,则循环循环法将确保前N-1回合是正确的。此后,该算法是周期性的:N第一轮将与第一轮相同。

因此,当且仅当programme_length < number_participants且参与者数量为偶数时,才有解;在这种情况下,循环算法将找到解。

如果参与者的数量是单数,那么在节目的每一天,必须至少有一个人没有配对。循环锦标赛在这种情况下仍然可以应用:增加一个额外的人(通常称为bye-player)。就算法而言,虚拟人的行为与正常人完全一样。每一轮,都会有一个不同的真人与假人配对,这意味着这一轮他们不会与真人配对。使用此方法,您只需programme_length <= number_participants

803