时间戳

首页 > 解决方案 > 在数据结构上使用记忆的递归

python - 在数据结构上使用记忆的递归

问题描述

我正在尝试对以下问题实施记忆。数据结构如下：

ROWS = {368: [247, 257], 257: [368], 2468: [357], 357: [2468], 358: [247], 247: [358, 368]}

它是一个字典，其中键的值作为列表。在每个键的每个列表中，元素包含与键不同的数字。示例：如果我们取键 368 : [247, 257] 我们观察到 247 不包含其键 368 中的任何数字。257 和 368 也是如此，不同的数字。

问题如下： 使用此数据结构构造一堵一定高度的墙，数字在彼此的顶部，使得没有邻居具有相同的数字。例如，第 4 层的墙将是：

1. 368, 247, 358, 247
2. 368, 257, 368, 257 ... and so on.

问题是：有多少种可能的高度 n 组合（在我们的例子中是 4）？

从单个元素开始时，我提出了基本的递归且非常无效且不优雅的解决方案：

ROWS = {368: [247, 257], 257: [368], 2468: [357], 357: [2468], 358: [247], 
247: [358, 368]} 
SUM=0

def count_configurations( elem , rows ) :
   global SUM
   if rows == 1 :
      SUM += len(ROWS[elem])
      return len(ROWS[elem])
   else:
      for k in ROWS[elem] :
         count_configurations( k, rows-1 )

它工作得很好，但是当我们在没有记忆的情况下上升到更高的高度时，它会永远存在。此外，如果尝试返回 count_configurations(k, rows-1)，它会在第一个元素处返回并退出并给出不正确的答案。问题是，在处理这个问题时，我们没有像斐波那契那样返回数字，但我们将返回一些其他列表。示例：对于第 4 级，将类似于：

(368, 4) : [(247:3), (257:3)]   (composed of 2 elements of level 3, then 
(247:3) :  [(358:2), (368:2)]  and  (257:3) :[(368,2)] (composed of elements of level 2)

依此类推，直到我们最终达到可以用实际值替换的第 1 级：

(368,1)=2 , (247, 1) = 1 , etc ...

在这种情况下可以实施记忆吗？我是否使用了错误的数据结构并且我处理了复杂的事情？你能给我一些关于如何简化事情的建议吗？

提前谢谢了。

标签： pythonrecursionmemoization

解决方案

记忆似乎在这里工作正常：

>>> from functools import lru_cache
>>>
>>> @lru_cache(None)
... def count_configurations( elem , rows ) :
...     if rows == 1 :
...         return len(ROWS[elem])
...     else:
...         return sum(count_configurations( k, rows-1 ) for k in ROWS[elem])

例子：

>>> count_configurations(247, 30)
2178309
>>> count_configurations(368, 100)
927372692193078999176
>>> count_configurations(357, 100)
1
>>> count_configurations(257, 100)
573147844013817084101

推荐阅读