Python深度列表比较

Question

我目前正在为Python编写一个数独求解程序。这是我目前有：

#!/usr/bin/env python 
"""Reads in a file formatted with nine lines each of which has nine characters 
corresponding to a sudoku puzzle. A blank is indicated by the value '0' 
Eventually should output a solution to the input puzzle""" 

import sys 

class cell: 
    value = 0 
    """Value of 0 means it is undetermined""" 

    def __init__(self, number): 
     self.value = number 
     self.possible = [2, 2, 2, 2, 2, 2, 2, 2, 2] 
     """Possibility a given value can be the number. 0 is impossible, 1 is definite, 2 is maybe""" 



    def selfCheck(self): 
     """Checks if the cell has only one possible value, changes the value to that number""" 
     if self.value == 0: 
       if self.possible.count(2) == 1: 
       """If there's only one possible, change the value to that number""" 
       i = 1 
       for item in self.possible: 
        if item == 2: 
         self.value = i 
         self.possible[i-1] = 1 
        i+=1 

def checkSection(section): 
    """For any solved cells in a section, marks other cells as not being that value""" 
    for cell in section: 
     if cell.value != 0: 
      for otherCell in section: 
       otherCell.possible[cell.value-1] = 0 

def checkChunk(chunk): 
    """Checks a chunk, the set of rows, columns, or squares, and marks any values that are impossible for cells based on that 
    chunk's information""" 
    for section in chunk: 
     checkSection(section) 

def selfCheckAll(chunk): 
    for section in chunk: 
     for cell in section: 
      cell.selfCheck() 

cellRows = [[],[],[],[],[],[],[],[],[]] 
cellColumns = [[],[],[],[],[],[],[],[],[]] 
cellSquares = [[],[],[],[],[],[],[],[],[]] 

infile = open(sys.argv[1], 'r') 
"""Reads the file specified on the command line""" 

i = 0 
for line in infile: 
    """Reads in the values, saves them as cells in 2d arrays""" 
    line = line.rstrip('\n') 
    for char in line: 
     row = i/9 
     column = i%9 
     newcell = cell(int(char)) 
     cellRows[row].append(newcell) 
     cellColumns[column].append(newcell) 
     row = (row/3)*3 
     column = column/3 
     square = row+column 
     cellSquares[square].append(newcell) 
     i+=1 
i = 0 
while i<50: 
    checkChunk(cellRows) 
    checkChunk(cellColumns) 
    checkChunk(cellSquares) 
    selfCheckAll(cellRows) 

    i+=1 

displayRow = [] 
for row in cellRows: 
    for cell in row: 
     displayRow.append(str(cell.value)) 

i = 0 
while i < 9: 
    output1 = ''.join(displayRow[9*i:9*i+3]) 
    output2 = ''.join(displayRow[9*i+3:9*i+6]) 
    output3 = ''.join(displayRow[9*i+6:9*i+9]) 
    print output1 + ' ' + output2 + ' ' + output3 
    if i%3 == 2: 
     print 
    i+=1 

我的问题是：

i = 0 
while i<50: 
    checkChunk(cellRows) 
    checkChunk(cellColumns) 
    checkChunk(cellSquares) 
    selfCheckAll(cellRows) 

    i+=1 

我想，直到它检测到没有从以前的迭代，而不是目前硬编码50的变化来运行代码倍。这可能是因为不再有合理的下一步（需要开始暴力强制值），或者谜题完全解决。无论哪种方式，我都需要对当前数据集中的一个（比如cellRows）进行深层复制，以便与通过checkChunk函数时实际副本发生的更改进行比较。

在Python中有这样的东西吗？ （如果有更好的方法来检查我是否完成，那也可以，但是现在我更感兴趣，如果我可以做深入的比较。）

编辑 - 我试图使用copy.deepcopy 。虽然这创建了一个很好的深层副本，但使用'=='检查两者之间的相等性总是返回false。

Answer 1

通过比较str()可以进行非常粗略的比较。当然不是最好的办法，但考虑到列表的复杂性，它可能是没问题的。

如果你想要更稳固的东西，你可以编写一个递归函数来处理它。

Answer 2

标准copy模块提供了通用深度复制设施：您正在搜索的是copy.deepcopy函数。

Answer 3

你总是可以腌制对象并将它们作为字符串进行比较。将它们转换为JSON字符串可能是最简单的方法之一。我怀疑这样做有更省资源的方式，但它工作得很好。这里是一个例子：

>>> from simplejson import dumps 
>>> ls1 = [1, [2, 3], [4, [5, 6]]] 
>>> ls2 = [1, [2, 3], [4, [5, 6]]] 
>>> dumps(ls1) == dumps(ls2) 
True 
>>> 

Answer 4

我不确定比较字符串表示是要走的路，但如果性能是一个问题，我猜你可以基准。下面是在深/递归列表比较的实现一个快速的尝试：

from itertools import izip 

def list_compare(a, b): 
    if type(a) != type(b): 
     return False 
    if type(a) != list: 
     return a == b 
    if len(a) != len(b): 
     return False 
    for a_, b_ in izip(a, b): 
     if not list_compare(a_, b_): 
      return False 
    return True 

它比较使用常规的相等运算符递归列表和非列表项。

Answer 5

就你而言，这只是一个二维列表。因此，将它们转换为单维字符串列表并进行比较将使代码最小。

list_of_list = [[1, 2, 3, 4, 5, 6, 7, 8], [2, 3, 4, 5, 6, 7, 8, 1], [3, 4, 5, 6, 7, 8, 1, 2], [4, 5, 6, 7, 8, 1, 2, 3], [5, 6, 7, 8, 1, 2, 3, 4], [6, 7, 8, 1, 2, 3, 4, 5], [7, 8, 1, 2, 3, 4, 5, 6], [8, 1, 2, 3, 4, 5, 6, 7]] 
current_iteration = ",".join(["".join(map(str, row)) for row in list_of_list]) 
previous_iteration = ",".join(["".join(map(str, row)) for row in list_of_list]) 
if current_iteration == previous_iteration: 
    return 

一旦生成字符串，您可以用相同的方式转换比较板，并以相同的方式进行比较。

不过，我会建议他们作为比较直接名单将有更多更简单的阅读

previous_iteration = [[1,2,3], [2,3,1], [3,1,2]] 
current_iteration = [[1,2,3], [2,3,1], [3,1,2]] 

if len(current_iteration) != len(previous_iteration): 
# This check is not required in your case as the lengths will be same for all iterations 
    return False 

for index, item_list in enumerate(current_iteration): 
    if item_list != previous_iteration[index]: 
     return False 

return True