J'essaie de générer toutes les séquences de clavier possibles (longueur de 7 chiffres que maintenant). Par exemple, si le clavier mobile ressemble à ceci: Certaines séquences possibles peuvent être: 123698 L'exigence est que le chiffre de chiffre doit être voisin du chiffre précédent. Voici comment je envisage de commencer ceci: Les informations sur Le voisin change de clavier au clavier, nous devons donc le calculer comme ceci: Je vais passer à travers tous les chiffres et ajouterai l'un des voisins possibles jusqu'à ce qu'il soit nécessaire jusqu'à ce que nécessaire La longueur est atteinte. EDIT: Voisins mis à jour, Aucune diagonale autorisée
Edit 2: Les chiffres peuvent être réutilisés
147896
125698
789632
6 Réponses :
C'est un algorithme récursif classique. Quelque pseudo code pour montrer le concept:
Est-ce comment les gens programment réellement dans des langues non dynamiques? Pourquoi ne pas simplement utiliser une table de hachage dans des listes de chiffres voisins comme OP suggéré? Vous n'avez même pas besoin de fonctions de première classe pour cela.
@aaron, certaines personnes viennent de programmer comme ça. Peu importe que la langue soit dynamique ou non. Par exemple, votre propre réponse ici n'utilise aucune fonctionnalité dynamique.
Cette solution est vraiment étroitement couplée à la disposition du clavier, d'autant plus que l'OP indiquait que "les informations sur le voisin passe du clavier au clavier" ne va pas à -1 car ce n'est pas strictement faux, mais ce n'est pas très réutilisable pour d'autres dispositions clés.
C'est le code Psuedo. Le but est de montrer l'algorithme dans un format facilement lisible et non de la manière dont vous l'appliquez réellement.
def keypadSequences(length):
return map(lambda x: '0'*(length-len(repr(x)))+repr(x), range(10**length))
keypadSequences(7)
Cela vient d'imprimer toutes les séquences numériques possibles. Il y a des règles dans le problème sur ce que le prochain numéro dans la séquence peut être.
Oui, lisez mon commentaire ci-dessus. J'ai remarqué la chose des voisins après mots. Ce serait la réponse sans conditions de voisinage
gen_neighbor_permutations(n=3, current_prefix='', available_digit_set=start_set, unique_digits = True)
Essayez ceci. Ceci produira toutes les séquences possibles. Vous n'avez pas mentionné si vous vouliez des cycles en eux, par exemple (0, 8, 9, 8) code> donc je les ai laissés dans. Si vous ne le voulez pas, alors utilisez simplement P> stack.extend(cur + (d, )
for d in neighbors[cur[-1]]
if d not in cur)
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())
Recursion n'est pas vraiment une grande partie d'un problème car la séquence est relativement courte, comme les choix de chaque chiffre, à l'exception du premier - il semble que "seulement" soit "seulement" de 4790 possibilités de désintégration des diagonales. Ceci est écrit comme un itérateur pour éliminer la nécessité de créer et de retourner un grand conteneur avec toutes les possibilités produites.
Cela me survienait qu'un avantage supplémentaire de l'approche axée sur les données consistant à stocker les informations d'adjacence voisine dans une structure de données (comme suggéré par l'OP) était que, outre supporter facilement différents claviers, il permet également de contrôler si des diagonales sont autorisées ou si pas trivial. p>
J'ai débattu de savoir s'il faut en faire une liste au lieu d'un dictionnaire pour des recherches plus rapides, mais que cela rendrait cela plus difficile à adapter pour produire des séquences autres que des chiffres (et ne feraient probablement pas de faire ça nettement plus rapide de toute façon). P>
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
C'est probablement une meilleure solution au problème que le mien.
Alors, quelle est votre question? Vous semblez comprendre le problème et vous avez commencé à démarrer la solution. Avec quoi as tu besoin d'aide? Comme indice possible, notez que toutes les séquences à 7 chiffres peuvent être trouvées en caculant toutes les séquences à 6 chiffres, puis en ajoutant tous les mouvements suivants possibles à chacun de ceux-ci. Toutes les séquences à 6 chiffres peuvent être FOUDN en calculant toutes les séquences à 5 chiffres ...
Vous êtes très incompatible avec vos voisins. Vous montrez que 0 a seulement 1 voisin, tandis que 1 a 3. Comptez-vous des diagonales ou non? Si oui, 2 devraient avoir 5 voisins, sinon, 1 ne devrait avoir que 2 voisins, etc.
Similaires à Stackoverflow. com / questions / 2893470 / ... , sauf les voisins sont définis différemment.
Merci pour la correction Jeff B, pas en comptant des diagonales. Modifié!
Les numéros peuvent-ils être utilisés plus d'une fois dans une séquence donnée ou s'agit-il d'un boggle où chacun ne peut être utilisé qu'une seule fois?
On dirait un solveur numérique à boggle!