优化匹配算法Runtim

Question

一个朋友最近让我编写一个算法，它取n个“人”，生成一个n-1乘n/2的网格，其中每个可能的对出现一次，在每个n/2部分中，任何人都不允许出现两次。（即person1与person2匹配，person1与person3匹配无效）。你知道吗

如果这不合理，想象一下这样的情景：为100个人创建99轮会议，每个人在每轮会议中都会遇到一个新的人，但没有人在一轮会议中有超过一个会议。这样，每轮举行50次独特的会议，共99轮，共计4950次独特的会议。你知道吗

我在python中使用递归回溯（不确定这是否是最好的方法）编写了这个代码。这个问题让我想起了数独，这是一个流行的数独解决方法）这需要一个愚蠢的时间，即使是很小的数字（例如50）。有没有一种更快的编码方法，或者我可以添加一些增强来让它运行得更快？你知道吗

代码在这里：https://pastebin.com/iyr2wdkz

import random
from itertools import combinations
import time as t
import sys
sys.setrecursionlimit(15000)

def isPrime(num):
    """Checks num for primality. Returns bool."""
     if num == 2:
        return True
    elif num < 2 or not num % 2: # even numbers > 2 not prime
        return False
        # factor can be no larger than the square root of num
    for i in range(3, int(num ** .5 + 1), 2):
        if not num % i: return False
    return True

def generatePrimes(n):
    """Returns a list of prime numbers with length n"""
    primes = [2,]
    noOfPrimes = 1  # cache length of primes for speed
    testNum = 3 # number to test for primality
    while noOfPrimes < n:
        if isPrime(testNum):
            primes.append(testNum)
            noOfPrimes += 1
        testNum += 2
    return primes



class Person: 
    def __init__(self, name, ID):
        self.name = name
        self.primeID = ID

    def __eq__(self, other):
        return self.primeID == other

    def __repr__(self):
        return '%d' % (self.name)

class Schedule:
    def __init__(self, numberofpeople):
        self.x = 0 #current x pos
        self.y = 0 #current y pos
        self.fill = 0 #number of slots filled
        self.board = [] #get initialized to an n-1 x n/2 grid  to hold links
        self.failed = [] #same as board but holds a list of failed links in each cell
        self.uniqueLinks = [] #list of unique links, a link is the product of two primes
        self.availableLinks = [] #links not yet placed in the grid
        self.personList = [] #list of Person. A person is a name and a unique prime number
        self.primeList = generatePrimes(numberofpeople) #list of the first n prime numbers
        random.shuffle(self.primeList)

        #initializes the empty lists
        for i in range(numberofpeople):
            self.personList.append(Person(i, self.primeList[i]))
        self.uniqueLinks = list(map(lambda x: x[0] * x[1], combinations(self.primeList, 2)))
        for i in self.uniqueLinks:
            self.availableLinks.append(i)
        tmp = len(self.uniqueLinks)
        for i in range(tmp // (numberofpeople // 2)):
            self.board.append(list())
            self.failed.append(list())
        for i in range(len(self.board)):
            for j in range(numberofpeople//2):
                self.board[i].append(None)
                self.failed[i].append(list())

    #checks if the candidate is valid in current position
    def isValid(self, candidate):
        factor1, factor2 = self.getFactor(candidate)
        for i in self.board[self.x]:
            if not i:
                return True
            if ((i % factor1) == 0) or ((i % factor2) == 0):
                return False
        return True

    #moves to the next non-None value, return True if successful
    def nextpos(self):
        for i in range(len(self.board)):
            for j in range(len(self.board[0])):
                if not self.board[i][j]:
                    self.x = i
                    self.y = j
                    return True
        return False

    #sets the last non-None value to None and adds that value to availableLinks and the failed tracker
    def prevpos(self):
        for i in range(len(self.board)-1, -1, -1):
            for j in range(len(self.board[0])-1, -1, -1):
                if self.board[i][j]:
                    self.x = i
                    self.y = j
                    tmp = self.board[self.x][self.y]
                    self.availableLinks.append(tmp)
                    self.board[i][j] = None
                    self.failed[i][j].append(tmp)
                    self.fill -= 1
                    random.shuffle(self.availableLinks)
                    return True


    #returns the prime factors of num
    def getFactor(self, num):
        for i in self.primeList:
            if num % i == 0:
                return i, num/i


    #recursive backtracking solving algorithm
    def solve(self):
        print('%d links placed, %d remaining, pos is %d, %d' % (self.fill, len(self.availableLinks), self.x, self.y))
        if not self.nextpos():
            return True
        for i in self.availableLinks:
            if self.isValid(i): and self.checkFail(i):
                self.fill += 1
                self.board[self.x][self.y] = i
                self.availableLinks.remove(i)
                if self.solve():
                    return True
                else:
                    self.prevpos()
        return False

    #replaces prime products with formatted names of people in the board
    def decompose(self):
        for i in range(len(self.board)):
            for j in range(len(self.board[0])):
                num1, num2 = self.getFactor(self.board[i][j])
                for k in self.personList:
                    if k == num1:
                        person1 = str(k)
                    if k == num2:
                        person2 = str(k)
                self.board[i][j] = person1 + '<-->' + person2


    # checks if num has already been tried at current pos, returns false if is has.
    def checkFail(self, num):
        if num in self.failed[self.x][self.y]:
            return False
        else:
            return True

    # verifies that the board has no duplicate values
    def verify(self):
        visited = []
        for i in self.board:
            for j in i:
                if j in visited:
                    print('Verification failed %s occurs twice'% j)
                    return False
                visited.append(j)
        print('Successfully verified')
        return True


s =Schedule(50)
s.solve()
s.verify()
s.decompose()
print(s.board)

Answer 1

看来你需要round-robin tournament algorithm。你知道吗

简言之：创建两行表，固定第一行的第一个条目，并循环移动所有其他条目（n-1次）。在每一个圆对是由相同的列中的顶部和底部条目组成的

0  1
2  3
  - pairs 0-2, 1-3
0  2
3  1
    pairs 0-3, 2-1
0  3
1  2
  - pairs 0-1, 3-2

Answer 2

多么惊人的代码量！你知道吗

这是scala中的一个解决方案。我只使用int，你可以映射到它个人ID地址：

def greetAsMad (persons: List [Int]) : List [(Int, Int)] = 
  if (persons.size < 2) Nil else 
  persons.tail.map (p=> (persons.head, p)) ::: greetAsMad (persons.tail)

对于100人，它会立即返回（<；200毫秒）。你知道吗

为了适应更多的人，我会把它转换成一个尾部递归函数。你知道吗

想法是，第一个人向所有人打招呼，然后离开房间。然后第二个人向大家打招呼，也离开了。最后99人向100人打招呼，两人都离开了房间。你知道吗

然后他们开始吃喝。你知道吗

以下是一种非递归方法：

for (i <- 1 to 99;
     j <- i + 1 to 100) yield (i, j)