最长多米诺骨牌序列

Question

编辑：新代码。这两种解决方案都非常有效，但由于某种原因并没有改善我的时间效果，这对我来说还没有意义

看到我的绝望，一位朋友向我推荐了他的解决方案，该方案在给定的时间内运行良好，但不知何故在这一特定输入上失败了：

9
1 2  2 3  3 4  4 5
3 6  6 7  3 8  8 9  9 10

它给出的是“9”而不是“5”。你知道为什么会这样吗

maxNum = int(0)
idxArr = []
def ReadInput():
    global array
    global firstNum
    arr = input().split()
    firstNum = int(arr[0])
    while int(arr[0]) * 2 + 1 > len(arr):
        tempArray = input().split()
        arr = arr + tempArray
    iterator = int(0)
    array = [0] * int(arr[0])
    for i in range(1, int(arr[0]) * 2, 2):
        tempArray = [0] * 3
        tempArray[0] = int(arr[i])
        tempArray[1] = int(arr[i + 1])
        tempArray[2] = None
        array[iterator] = tempArray
        iterator+=1

def SortArray(array):
    array.sort(key=lambda x: x[1])
    array.sort(key=lambda x: x[0])

def MergeDominos(array):
    tempNum = int(0)
    for item in array:
        if (item[2] == None):
            iterator = tempNum
            counter = int(0)
            tempBool = False
            try:
                while item == array[iterator]:
                    if (tempBool):
                        array.pop(iterator)
                        counter += 1
                    else:
                        iterator += 1
                        counter += 1
                        tempBool = True
            except IndexError:
                True == True
            if (counter % 2 == 1):
                item[2] = counter
                tempNum += 1
            else:
                tempItem = item.copy()
                array.insert(tempNum + 1, tempItem)
                array[tempNum + 1][2] = int(1)
                item[2] = counter - 1
                tempNum += 1
        else:
            tempNum += 1

def GetLengthOfArray(array):
    counter = int(0)
    for item in array:
        counter += item[2]
    return counter

def SwitchPlaces(item):
    item[0], item[1] = item[1], item[0]

def GetMaxLength(array, tempArray, left, right):
    global maxNum
    # print("This is temp: ", tempArray)
    for i in range(len(array)):
        # print("Testing: ", array[i], "Iteration: ", i)
        # print("IdxArr: ", idxArr)
        if (len(array) <= len(idxArr)):
            #print("BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE ")
            break
        if (i not in idxArr):
            #print("Condition:")
            if (left == array[i][0]):
                #print("LL")
                if (i in idxArr):
                    break
                else:
                    idxArr.append(i)
                SwitchPlaces(array[i])
                if (len(array) >= len(idxArr)):
                    tempArray.insert(0, array[i])
                if (GetLengthOfArray(tempArray) > maxNum):
                    maxNum = GetLengthOfArray(tempArray)
                if (len(array) >= len(idxArr)):
                    GetMaxLength(array, tempArray, tempArray[0][0], tempArray[len(tempArray) - 1][1])
            if (left == array[i][1]):
                #print("LR")
                if (i in idxArr):
                    break
                else:
                    idxArr.append(i)
                if (len(array) >= len(idxArr)):
                    tempArray.insert(0, array[i])
                if (GetLengthOfArray(tempArray) > maxNum):
                    maxNum = GetLengthOfArray(tempArray)
                if (len(array) >= len(idxArr)):
                    GetMaxLength(array, tempArray, tempArray[0][0], tempArray[len(tempArray) - 1][1])
            if (right == array[i][0]):
                #print("RL")
                if (i in idxArr):
                    break
                else:
                    idxArr.append(i)
                if (len(array) >= len(idxArr)):
                    tempArray.append(array[i])
                if (GetLengthOfArray(tempArray) > maxNum):
                    maxNum = GetLengthOfArray(tempArray)
                if (len(array) >= len(idxArr)):
                    GetMaxLength(array, tempArray, tempArray[0][0], tempArray[len(tempArray) - 1][1])
            if (right == array[i][1]):
                #print("RR")
                if (i in idxArr):
                    break
                else:
                    idxArr.append(i)
                SwitchPlaces(array[i])
                if (len(array) >= len(idxArr)):
                    tempArray.append(array[i])
                if (GetLengthOfArray(tempArray) > maxNum):
                    maxNum = GetLengthOfArray(tempArray)
                if (len(array) >= len(idxArr)):
                    GetMaxLength(array, tempArray, tempArray[0][0], tempArray[len(tempArray) - 1][1])
            #else:
               # print("No condition BIG OOOF")

ReadInput()
SortArray(array)
MergeDominos(array)
for i in range(len(array)):
    #print("iter num: ", i)
    tempArray = []
    idxArr = []
    idxArr.append(i)
    tempArray.append(array[i])
    if (GetLengthOfArray(tempArray) > maxNum):
        maxNum = GetLengthOfArray(tempArray)
    GetMaxLength(array, tempArray, tempArray[0][0], tempArray[len(tempArray) - 1][1])
print(maxNum)

E1：输入是以这种奇怪的方式进行的，因为列表的第一项给出了多米诺骨牌的数量，而且输入可以分为多行，然后我创建列表项对

输入示例：

5 1 2
1 2
2 3
2
17
2 17

多米诺骨牌是：

[('1','2'),('1','2'),('2','2'),('2','17'),('2','17')]

预期结果：

5

（3,2）-（2,1）-（1,2）-（2,17）-（17-2）

Answer 1

尝试以下解决方案：

def solution(dominoes):
    if len(dominoes) == 0:
        return 0

    def get_sequence(d, sol=None):
        if sol is None:
            sol = []

        if len(d) == 0:
            return

        for i in range(len(d)):
            rest = d[:i] + d[i+1:]
            d1, d2 = d[i], d[i][::-1]

            if d1 == d2:
                if (not sol) or (sol[-1][1] == d1[0]):
                    yield sol + [d1]
                    yield from get_sequence(rest, sol + [d1])
            else:
                if (not sol) or (sol[-1][1] == d1[0]):
                    yield sol + [d1]
                    yield from get_sequence(rest, sol + [d1])

                if (not sol) or (sol[-1][1] == d2[0]):
                    yield sol + [d2]
                    yield from get_sequence(rest, sol + [d2])


    return(len(max(get_sequence(dominoes), key=len)))

dominoes = [('1','2'),('1','2'),('2','2'),('2','17'),('2','17')]
print(solution(dominoes))

印刷品：

5

Answer 2

以下是对您的解决方案的重写，其中有一个重大更改：

if maximum == len(listOfDominos) + len(tempList):
    break

这会阻止代码在知道无法改进的最大值时进一步探索。对于您提供的示例输入，它将搜索数量减少了20倍：

def find(listOfDominos, tempList):
    maximum = len(tempList)

    for currentDominoIndex, domino in enumerate(listOfDominos):
        if maximum == len(listOfDominos) + len(tempList):
            break  # we can't do any better, so why try?

        remainingDominos = listOfDominos[:currentDominoIndex] + listOfDominos[currentDominoIndex+1:]

        if tempList:
            backwardDomino = domino[::-1]
            head, tail = tempList[0], tempList[-1]

            if domino[1] == head[0]:
                maximum = max(find(remainingDominos, [domino] + tempList), maximum)
            elif backwardDomino[1] == head[0]:
                maximum = max(find(remainingDominos, [backwardDomino] + tempList), maximum)
            elif domino[0] == tail[1]:
                maximum = max(find(remainingDominos, tempList + [domino]), maximum)
            elif backwardDomino[0] == tail[1]:
                maximum = max(find(remainingDominos, tempList + [backwardDomino]), maximum)
        else:
            maximum = max(find(remainingDominos, [domino]), maximum)

    return maximum

listOfNumbers = input().split()

numberOfDominos = int(listOfNumbers.pop(0))

while numberOfDominos * 2 > len(listOfNumbers):
    listOfNumbers += input().split()

listOfDominos = list(zip(listOfNumbers[0::2], listOfNumbers[1::2]))

print(find(listOfDominos, []))

尝试一下，看看它是否能在不引入任何错误的情况下提高性能