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

Question

我正在尝试生成所有可能的小键盘序列（目前只有7位数字长度）。例如，如果移动键盘如下所示：

1 2 3
4 5 6
7 8 9
  0

一些可能的序列可以是：

123698
147896
125698
789632

要求数字的每一位都应该是前一位的邻居。在

以下是我计划如何开始的：

关于邻居的信息会随着键盘的不同而变化，所以我们必须这样硬编码：

^{pr2}$

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

编辑：更新的邻居，不允许对角线 编辑2：数字可以重复使用

Answer 1

递归在这里并不是什么大问题，因为序列相对较短，除了第一个数字外，每个数字的选择也相对较短，因此似乎“只有”4790个不允许使用对角线的可能性。这是作为迭代器编写的，以消除创建和返回包含所有可能的大型容器的需要。在

我突然想到，在数据结构中存储邻居邻接信息的数据驱动方法的另一个好处是，除了容易支持不同的小键盘之外，它还使得控制对角线是否被允许变得微不足道。在

我简短地讨论了是否将其列为一个列表而不是一个字典，以便更快地查找，但我意识到这样做会使生成除数字以外的序列变得更困难（而且可能也不会使它更快）。在

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

def adj_sequences(ndigits):
    seq = [None]*ndigits  # pre-allocate

    def next_level(i):
        for neighbor in adjacent[seq[i-1]]:
            seq[i] = neighbor
            if i == ndigits-1:  # last digit?
                yield seq
            else:
                for digits in next_level(i+1):
                    yield digits

    for first_digit in range(10):
        seq[0] = first_digit
        for digits in next_level(1):
            yield digits

cnt = 1
for digits in adj_sequences(7):
    print '{:d}: {!r}'.format(cnt, ''.join(map(str,digits)))
    cnt += 1

Answer 2

试试这个。在

 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)，所以我把它们留在了里面。如果你不想要，那就用

^{pr2}$

请注意，我为0创建了一个包含一个元素的列表，而不是一个整数。这是为了保持一致性。很高兴能在字典里查到索引，知道你会得到一个列表。在

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

Answer 3

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

def gen_neighbor_permutations(n, current_prefix, available_digit_set, removed_digits=set(), unique_digits=False):
    if n == 0:
            print current_prefix
            return
    for d in available_digit_set:
            if unique_digits:
                    gen_neighbor_permutations(n-1, current_prefix + str(d), set(neighbors[d]).difference(removed_digits), removed_digits.union(set([d])), unique_digits=True )
            else:
                    gen_neighbor_permutations(n-1, current_prefix + str(d), set(neighbors[d]).difference(removed_digits) )

gen_neighbor_permutations(n=3, current_prefix='', available_digit_set=start_set)

我还忍不住注意到，在您的示例中，没有一个数字被重用。如果您希望这样做，那么可以使用unique_digits = True选项；这将不允许对已经使用的数字进行递归。在

+1多有趣的拼图。我希望这对你有用！在

^{pr2}$