Recherche d'une formule pour calculer le voisinage d'un point

Bonjour à vous, j'essaye de programmer en python un algorithme qui me permet de calculer le voisinage à n saut d'un point précis. Exemple: soit le carré suivant

00 01 02 03 05

06 07 08 09 10

11 12 13 14 15

16 17 18 19 20

le voisinage à un saut de 0 est 1, 6 et 7. A deux sauts, 2, 8, 13, 11 et 12. Ainsi de suite? Il faut pouvoir calculer pour chaque point, son voisinage à n sauts. Je voudrais savoir si quelqu'un connaît une formule mathématique qui pourrait s'appliquer dans mon cas, parce que je galère vraiment Merci d'avance.

Salut.

Avant de répondre, une petite précision: est-ce que 0, 1, 6 et 7 sont accessibles depuis 0 en 2 sauts?

Pour l'algorithme suivant, je prends comme hypothèse que c'est le cas.

Prenons la fonction (O) jump(p, n) qui prend un point p de ta matrice et un nombre n et retourne une liste de points O.

Il te faudra aussi la fonction O neighbors(p) qui prend un point p et retourne une liste de points O. La sémantique de cette fonction est qu'elle donne tous les points qui sont voisins du point donné. (Je suppose que tu peux implémenter cette fonction toi même, mais n'hésite pas si tu as des soucis.)

Après donné un point p et n sauts il suffit d'appeler jump(p, n), retournant ta liste de points O et le nombre 0. Plus explicitement, jump ressemble à:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

O jump(p, n)

If(n == 1)
  Return (neighbors(p))
Else
  O = jump(p)
  K (liste of points)
  Foreach o in O
    K.add(jump(o, n-1))
  End
  Return K
End

Si j'ai pas fait d'erreur stupide, l'idée devrait marcher. Note que la liste de point n'est pas distincte, dans le sens que un point apparaitra plusieurs fois. C'est aussi un algorighme naïf qui utilise une structure de données extrêmement simple (une matrice), s'il te faut quelque chose de plus efficace, c'est possible.

Tu cherches une formule explicite, ou un algorithme qui calcule les voisinages ? Pour un algo, je n'y ai pas trop réfléchi mais ça fait un peu de temps que je n'ai pas programmé.

Par contre, si tu veux une formule explicite, je pense que c'est ta représentation d'un carré qui n'est pas bonne,. La représentation sous forme de couples (m, n) avec m et n deux entiers devrait te faciliter la vie.

As-tu le choix dans la représentation de tes donnés ? Si c'est le cas, je te recommande de représenter par exemple le nombre 00 par le couple (0, 0), le nombre 03 par le couple (0, 3) et le nombre 14 par le couple (2, 3). Comme un repère cartésien avec l'origine en haut à gauche. Ça devrait être plus facile de trouver une formule.

Si tu ne peux pas faire cela à cause de tes contraintes, on devrait s'en sortir quand même, mais ça va être chiant parce qu'il y a plein de cas (voisinage pas trop grand ? le point dont on prend le voisinage est-il trop près du bord ? etc.)

Je rajoute que si tu as la possibilité de remplacer tes entiers par des couples, il sera toujours possible de trouver une bijection qui retransformera tes couples en entiers comme au départ.

Non 0 n'a pour voisin à un saut que 1, 6 et 7. Par contre j'ai pas très bien saisi ton algorithme

C'est un algorithme que je voudrais en fait. Oui j'ai le choix sur la représentation de données.

0 a pour voisin à 1 saut 1, 6 et 7. 1 a comme voisin à 1 saut 0, 2, 6, 7 et 8. Tu peux donc, en partant de 0, faire un saut et arriver à 6 puis retourner à 0 en un saut. 0 est donc atteignable depuis 0 en deux sauts, correct?

L'algorithme est basé sur un simple principe récursif. Tu peux rejoindre en un saut tous les voisins d'un point. (If condition)

Pour plus d'un saut du point p, disons n+1, tu peux rejoindre tous les points joignable en n sauts depuis les voisins de p. (Else condition)

Merci à vous, et particulièrement à c_pages, ton explication sur les couples (i,j) m'a sauvé sur ce coup. Depuis le début de la semaine je galérais sur cet algorithme. J'espère que je te revaudrais ça un jour

Vive le Zeste du savoir!!