python - 优化匹配算法运行时

Question

一位 friend 最近要求我编写一个算法，该算法需要 n 个“人”并生成 n-1 x n/2 网格，其中每个可能的对都出现一次，并且在每个 n/2 部分中，不允许任何人出现两次。 (即 person1 与 person 2 匹配，person1 与 person3 匹配无效)。

如果这没有意义，请想象一下:对于 100 个人，创建 99 轮 session ，每个人在每一轮中都会遇到新的人，但没有人在一轮中会面超过一次。这样每轮发生 50 次独特的 session ，共 99 轮，总计 4950 次独特的 session 。

我已经使用递归回溯在 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

多么可观的代码量!

这是 scala 中的一个解决方案。我只使用 Ints，您可以将其映射到 Person.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 毫秒)。

为了准备更多的人，我会把它变成一个尾递归函数。

想法是，第 1 个人向所有人打招呼，然后离开房间。然后第 2 个人跟大家打招呼，也离开了。最后，第 99 个人与第 100 个人打招呼，两人都离开了房间。

然后他们开始吃喝。

这是一个非递归的方法:

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