Generate all possible numpad/keypad sequences

Question

I am trying to generate all possible keypad sequences (7 digit length only right now). For example if the mobile keypad looks like this:

1 2 3
4 5 6
7 8 9
  0

Some of the possible sequences can be:

123698
147896
125698
789632

The requirement is that the each digit of number should be neighbor of previous digit.

Here is how I am planning to start this:

The information about the neighbor changes from keypad to keypad so we have to hardcode it like this:

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]}

I will be traversing through all digits and will append one of the possible neighbors to it until required length is achieved.

EDIT: Updated neighbors, no diagonals allowed EDIT 2: Digits can be reused

Answer 1

Try this.

 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))

This will produce all possible sequences. You didn't mention if you wanted ones that have cycles in them, for example (0, 8, 9, 8) so I left them in. If you don't want them, then just use

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

Note that I made the entry for 0 a list with one element instead of just an integer. This is for consistency. It's very nice be able to index into the dictionary and know that you're going to get a list back.

Also note that this isn't recursive. Recursive functions are great in languages that properly support them. In Python, you should almost always manage a stack like I demonstrate here. It's just as easy as a recursive solution and sidesteps function call overhead (python doesn't support tail recursion) and maximum recursion depth concerns.

Answer 2

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)

I also couldn't help but notice that in your examples, none of the digits are reused. If you want that, then you would use the unique_digits = True option; this will disallow recursion on digits that are already used.

+1 What a fun puzzle. I hope this works for you!

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