生成所有可能的数字键盘序列

8 投票
6 回答
1169 浏览
提问于 2025-04-16 07:28

我正在尝试生成所有可能的手机键盘序列(目前只考虑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:数字可以重复使用。

6 个回答

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
1
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 这个谜题真有趣。希望这对你有帮助!

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

试试这个。

 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不支持尾递归)和最大递归深度的问题。

撰写回答