生成所有可能的小键盘/小键盘序列

Question

我正在尝试生成所有可能的键盘序列(目前只有7位数长度).例如,如果移动键盘如下所示:

1 2 3
4 5 6
7 8 9
  0

一些可能的序列可以是:

123698
147896
125698
789632

要求是数字的每个数字应该是前一个数字的邻居.

以下是我计划如何开始这个:

有关邻居的信息从键盘变为键盘,因此我们必须对其进行硬编码:

neighbors = {0: 8, 1: [2,4], 2: [1,3,5], 3: [2,6], 4: [1,5,7], 5: [2,4,6,8], 6: [3,5,9], 7: [4,8], 8: [7,5,9,0], 9: [6,8]}

我将遍历所有数字,并将附加一个可能的邻居,直到达到所需的长度.

编辑:更新的邻居,没有允许对角线编辑2:数字可以重复使用

Answer 1

尝试这个。

 neighbors = {0: [8], 
             1: [2,4], 
             2: [1,4,3], 
             3: [2,6], 
             4: [1,5,7], 
             5: [2,4,6,8], 
             6: [3,5,9], 
             7: [4,8], 
             8: [7,5,9,0], 
             9: [6,8]}


def get_sequences(n):
    if not n:
        return
    stack = [(i,) for i in  range(10)]
    while stack:
        cur = stack.pop()
        if len(cur) == n:
            yield cur
        else:
            stack.extend(cur + (d, ) for d in neighbors[cur[-1]]) 

print list(get_sequences(3))

这将产生所有可能的序列。你没有提到你是否想要那些有循环的，例如，(0, 8, 9, 8)所以我把它们留在了里面。如果你不想要它们，那么就使用

 stack.extend(cur + (d, ) 
              for d in neighbors[cur[-1]]
              if d not in cur)

请注意，我为列表创建了一个条目0，其中包含一个元素，而不仅仅是一个整数。这是为了一致性。能够索引到字典并知道您将得到一个列表是非常好的。

另请注意，这不是递归的。递归函数在正确支持它们的语言中非常有用。在 Python 中，您几乎应该始终管理堆栈，就像我在这里演示的那样。它就像递归解决方案一样简单，并且可以避免函数调用开销（Python 不支持尾递归）和最大递归深度问题。