Cómo enumerar todas las rutas en una cuadrícula 2D solo yendo hacia la derecha o hacia abajo desde (0,0) a (n-1, n-1)

Esta no es necesariamente la mejor opción, pero es una solución válida y ciertamente vale la pena conocerla, ya que es un algoritmo realmente útil: la próxima permutación. Ver permutación

def next_permutation(elems):
elems = list(elems)
N = len(elems) for k in range(N-2, -1, -1):
if elems[k] < elems[k+1]:
break
else:
raise StopIteration for l in range(N-1, -1, -1):
if elems[k] < elems[l]:
break elems[k], elems[l] = elems[l], elems[k]
elems[k+1:] = reversed(elems[k+1:]) return elems def all_permutations(elems):
elems = sorted(elems)
while True:
yield elems
elems = next_permutation(elems) for permutation in all_permutations([2, 3, 1]):
print(permutation)


def next_permutation(elems):
elems = list(elems)
N = len(elems) for k in range(N-2, -1, -1):
if elems[k] < elems[k+1]:
break
else:
raise StopIteration for l in range(N-1, -1, -1):
if elems[k] < elems[l]:
break elems[k], elems[l] = elems[l], elems[k]
elems[k+1:] = reversed(elems[k+1:]) return elems def all_permutations(elems):
elems = sorted(elems)
while True:
yield elems
elems = next_permutation(elems) for permutation in all_permutations([2, 3, 1]):
print(permutation)


def next_permutation(elems):
elems = list(elems)
N = len(elems) for k in range(N-2, -1, -1):
if elems[k] < elems[k+1]:
break
else:
raise StopIteration for l in range(N-1, -1, -1):
if elems[k] < elems[l]:
break elems[k], elems[l] = elems[l], elems[k]
elems[k+1:] = reversed(elems[k+1:]) return elems def all_permutations(elems):
elems = sorted(elems)
while True:
yield elems
elems = next_permutation(elems) for permutation in all_permutations([2, 3, 1]):
print(permutation)


def next_permutation(elems):
elems = list(elems)
N = len(elems) for k in range(N-2, -1, -1):
if elems[k] < elems[k+1]:
break
else:
raise StopIteration for l in range(N-1, -1, -1):
if elems[k] < elems[l]:
break elems[k], elems[l] = elems[l], elems[k]
elems[k+1:] = reversed(elems[k+1:]) return elems def all_permutations(elems):
elems = sorted(elems)
while True:
yield elems
elems = next_permutation(elems) for permutation in all_permutations([2, 3, 1]):
print(permutation)


def next_permutation(elems):
elems = list(elems)
N = len(elems) for k in range(N-2, -1, -1):
if elems[k] < elems[k+1]:
break
else:
raise StopIteration for l in range(N-1, -1, -1):
if elems[k] < elems[l]:
break elems[k], elems[l] = elems[l], elems[k]
elems[k+1:] = reversed(elems[k+1:]) return elems def all_permutations(elems):
elems = sorted(elems)
while True:
yield elems
elems = next_permutation(elems) for permutation in all_permutations([2, 3, 1]):
print(permutation)


def next_permutation(elems):
elems = list(elems)
N = len(elems) for k in range(N-2, -1, -1):
if elems[k] < elems[k+1]:
break
else:
raise StopIteration for l in range(N-1, -1, -1):
if elems[k] < elems[l]:
break elems[k], elems[l] = elems[l], elems[k]
elems[k+1:] = reversed(elems[k+1:]) return elems def all_permutations(elems):
elems = sorted(elems)
while True:
yield elems
elems = next_permutation(elems) for permutation in all_permutations([2, 3, 1]):
print(permutation)


def next_permutation(elems):
elems = list(elems)
N = len(elems) for k in range(N-2, -1, -1):
if elems[k] < elems[k+1]:
break
else:
raise StopIteration for l in range(N-1, -1, -1):
if elems[k] < elems[l]:
break elems[k], elems[l] = elems[l], elems[k]
elems[k+1:] = reversed(elems[k+1:]) return elems def all_permutations(elems):
elems = sorted(elems)
while True:
yield elems
elems = next_permutation(elems) for permutation in all_permutations([2, 3, 1]):
print(permutation)

que produce

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Puede usar esto para resolver su problema enumerando todas las permutaciones de la lista
['R'] * N + ['D'] * N
donde ‘R’ representa un movimiento hacia la derecha y ‘D’ representa un movimiento hacia abajo, lo que produce una secuencia de movimientos que corresponde a un camino. Luego puede convertir esto a su lista de waypoints.

(Por simplicidad vamos a modificarlo para que sea correcto o superior) y estamos llegando a (n, n)

Una implementación recursiva
Inicialmente estás en (0,0), ahora tienes dos opciones
1) ve a la derecha (1,0)
2) subir (0,1)
Así que generalicemos: donde sea que se encuentre, tiene estas dos opciones.
Pero en algunos casos no está permitido elegir las dos opciones.
Considere este caso: n = 10 y la posición actual es (5,10), por lo que no puede subir porque si quiere alcanzar (n, n) tendrá que bajar un paso que no está permitido.
Luego puede definir una función f (x, y, v) donde (x, y) son coordenadas de posición actuales y v es un contenedor para todos los movimientos pasados ​​que condujeron a esa posición.
Y también establezca un contenedor global g que contendrá todos los contenedores (rutas) generados a partir de la función.

Función f (x, y, v):
v.inserción (x, y)
if (x = ny e = n):
hemos alcanzado la posición deseada
g.insertar (v)
más:
si (x f (x + 1, y, v)
si (y f (x, y + 1, v)

Finalmente g contendrá todos los caminos.

Hay un enfoque de programación dinámica para este problema basado en el hecho de que si alcanzó algún punto (a, b) al generar estos caminos, y ya calculó el número de rutas desde ese punto hasta (n, n), entonces no es necesario hacerlo esto de nuevo.
Entonces, en lugar de generar esas rutas, puede obtener el número de rutas de (0,0) a (n, n) modificando la función anterior.

Función f (x, y):
si (x, y) se resolvió antes:
return res (x, y) \\\ fue resuelto antes ?? Devuelve su resultado
if (x = ny e = n):
retorno 1 \\\ hemos alcanzado la posición deseada
\\\ y esto significa que generamos una ruta
más:
res = 0
\\ evaluar las dos opciones
si (x res = res + f (x + 1, y)
si (y res = res + f (x, y + 1)
res (x, y) = res \\ guarda el resultado
volver res

res (x, y) significa el resultado guardado en la tabla dp

Como usted dice, el número de tales rutas es [matemática] {2n \ elegir n} [/ matemática], por lo que es probable que la lista se vuelva inmanejable muy rápidamente.

Una forma de hacerlo con programación dinámica es notar que:

caminos de (0,0) a (A, B) =
todas las rutas de (0,0) a (A-1, B) con (A, B) adjuntas
Unión
todas las rutas de (0,0) a (A, B-1) con (A, B) adjuntas

Sin embargo, DP realmente no le ahorra nada aquí, porque si bien visitará cada (A, B) solo una vez, el número de elementos en la lista en (A, B) será igual al número de rutas distintas a (A ,SI). Por lo tanto, también podría usar la búsqueda de profundidad, que usará menos memoria si puede consumir las rutas de una en una.

Primero debes saber matemáticamente cómo calcular esos caminos.

En una cuadrícula o matriz 2D, el número de rutas de (0,0) a (n-1, n-1)
son [(2n-2)! / {(n-1)!} ^ 2]

Pero es más importante saber cómo lo conseguimos.

De (0,0) a (n-1, n-1) hay n-1 bordes hacia abajo y n-1 bordes hacia la derecha. Piense como espacios en blanco como n-1 espacios en blanco en dirección horizontal y n-1 espacios en blanco en dirección vertical.

Cuando das un paso, significa que llenas un espacio en blanco. Pero recuerde que los espacios en blanco se llenan con pasos similares. Entonces, hay un total de 2 (n-1) espacios en blanco, con n-1 pasos similares en dirección horizontal y n-1 pasos similares en dirección vertical.

Ahora recuerda un poco los cálculos de probabilidad. Cuando permuta una palabra de longitud n con una sola palabra que aparece m veces, las permutaciones son n! / M !.

¡Así que simplemente hazlo aquí, por lo tanto [(2n-2)! / {(n-1)!} ^ 2].

Una vez que sepa las matemáticas, puede representar eso en su algoritmo, que es básicamente una simulación de sus matemáticas paso a paso.

Si aún necesita ayuda, hágamelo saber.