Генерация всех возможных последовательностей цифровой клавиатуры / клавиатуры

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

Я буду обходить все цифры и добавляю к нему одного из возможных соседей, пока не будет достигнута требуемая длина.

EDIT: обновлены соседи, диагонали не допускаются РЕДАКТИРОВАТЬ 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 не поддерживает хвостовую рекурсию) и проблемы максимальной глубины рекурсии.

Answer 2

Рекурсия на самом деле не является большой проблемой здесь, потому что последовательность относительно короткая, как и выбор для каждой цифры, кроме первой - так что, кажется, «только» будет 4790 возможностей, запрещающих диагонали.Это написано как итератор, чтобы исключить необходимость создания и возврата большого контейнера со всеми производимыми в нем возможностями.

Мне пришло в голову, что дополнительное преимущество управляемого данными подхода хранения информации о смежности соседей в структуре данных (как предложил OP) заключается в том, что, помимо простой поддержки различных клавиатур, он также позволяет контролировать наличие диагоналей.разрешены или нетривиальны.

Я кратко обсудил вопрос о том, следует ли сделать его списком вместо словаря для более быстрого поиска, но понял, что это затруднит адаптацию к созданию последовательностей, отличных от цифр (и, вероятно, не сделает этогозначительно быстрее в любом случае).

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 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 Какая забавная головоломка. Я надеюсь, что это работает для вас!

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

Answer 4

states = [
    [8],
    [2, 4],
    [1, 3, 5],
    [2, 6],
    [1, 5, 7],
    [2, 4, 6, 8],
    [3, 5, 9],
    [4, 8],
    [5, 7, 9, 0],
    [6, 8]
]

def traverse(distance_left, last_state):
    if not distance_left:
        yield []
    else:
        distance_left -= 1
        for s in states[last_state]:
            for n in traverse(distance_left, s):
                yield [s] + n

def produce_all_series():
    return [t for i in range(10) for t in traverse(7, i)]

from pprint import pprint
pprint(produce_all_series())

Answer 5

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 keyNeighborsRec(x, length):
    if length == 0:
            print x
            return
    for i in neighbors[x%10]:
            keyNeighborsRec(x*10+i,length-1)


def keyNeighbors(l):
    for i in range(10):
            keyNeighborsRec(i,length-1)

keyNeighbors(7)

это действительно легко без условия соседа ...

def keypadSequences(length):
    return map(lambda x: '0'*(length-len(repr(x)))+repr(x), range(10**length))

keypadSequences(7)

Answer 6

Это классический рекурсивный алгоритм. Некоторый псевдокод, чтобы показать концепцию:

function(numbers) { 
  if (length(numbers)==7) { 
    print numbers; 
    return; 
  } 
  if (numbers[last]=='1') { 
    function(concat(numbers,  '2')); 
    function(concat(numbers,  '4')); 
    return; 
  } 
  if (numbers[last]==='2') { 
    function(concat(numbers,  '1')); 
    function(concat(numbers,  '3')); 
    function(concat(numbers,  '5')); 
    return; 
  } 
  ...keep going with a condition for each digit..
}