2

El problema se basa en rellenar una matriz cuadrada de tamaño 'n' con todas las combinaciones posibles de 0 y 1.

Con n = 2:

[[0,0],[0,1],[1,0],[1,1]]

n =3 :

[[0,0,0],[0,0,1],[0,1,0],...,[1,1,1]]

El problema es que no sé porqué entra al if si el tamaño de la lista es mayor al tamaño, si alguien puede ayudarme desde ya le agradezco. Adjunto el código

global tam
tam=3
def matriz(candidato):
    if(len(candidato)<tam):
        auxi=candidato
        auxi.append(0)
        matriz(auxi)
        print(candidato)
        auxd=candidato
        auxd.append(1)
        matriz(auxd)
    else:
        print(candidato)


matriz([])
3
  • osea este codigo no crea la matriz, pero si se puede mostrar por consola en la parte de el else basta con ponerle un append a otra lista, el problema es que no entiendo porque no funciona la recursividad
    – brandi003
    Commented el 14 oct. 2019 a las 11:22
  • No es que te entre por el if a pesar de que len sea mayor que 3, es que ya había entrado cuando len era menor que 3. Es difícil de explicar, pero si lo ejecutas paso a paso con un depurador lo verás. Mientras len es menor que 3, entra por el if, y llega a la línea en que se llama recursivamente a sí misma. Una vez la recursión termina y retorna a ese punto, hace el print y sigue por la línea siguiente. Para entonces len ya es mayor que 3, debido a las llamadas recursivas, pero sigue dentro del if por lo que el append(1) se va a hacer sobre la lista existente.
    – abulafia
    Commented el 14 oct. 2019 a las 12:04
  • Al margen de esta farragosa explicación de por qué no se comporta como esperabas, decirte que en general va por mal camino. La idea tal como yo lo veo es distinita. La recursividad se basa en "supongamos que tengo una función que me resuelve el problema para un tamaño n, y usemos esa solución para construir la de tamaño n+1". Piensa sobre esto. Y luego resulta que la que te resuelve tamaño n es la misma función que la que resuelve n+1, por eso se llama a sí misma
    – abulafia
    Commented el 14 oct. 2019 a las 12:06

3 respuestas 3

3

En toda función recursiva tienes que tener claro dos cosas:

  • cuál es la operación que "induce" el resultado de n+1 a partir de n
  • cuál es la condición de corte (o sea, cómo acaba la recursión)

Si tenemos matrix(n), la forma de calcular matrix(n+1) es:

matrix(n+1) <- [ [i]+item for i in (0,1) for item in matrix(x) ]

La condición de corte será qué pasa cuando n==0:

matrix(0) <- [[]]

Juntando todo:

def matrix(n: int):
    if n==0:
        return [[]]
    else:
       m = matrix(n-1)
       return [[i]+item for i in (0,1) for item in m]

Poner como condición de corte matrix(0) == [[]] suele dar algo de confusión. La función matrix debe devolver una lista de listas y el elemento vacío [] no es correcto. (El [[]] se denomina elemento inicial de la categoría a partir del cuál se puede sacar el resto).

2
  • Buena respuesta (+1) y código super-compacto! Te me has adelantado escribiendo tu respuesta mientras yo redactaba mi larga explicación, pero veo que en esencia decimos lo mismo, aunque yo no quise dar código. ¿Debería borrar mi respuesta?
    – abulafia
    Commented el 14 oct. 2019 a las 15:16
  • @abulafia Creo que no son excluyentes. Mi respuesta es bastante concisa, pero en la tuya haces una comparación con la respuesta aceptada de Yeste que puede ser interesante. Si sobra alguna respuesta sería la mía. Commented el 14 oct. 2019 a las 18:21
2

Bien, viendo que la implementación quizás no es la más adecuada, te propongo la siguiente:

def matrix(length, combinationVector, fullMatrix):
    if len(combinationVector) <= length:
        matrixToFillWithOne = combinationVector.copy()
        matrixToFillWithZero = combinationVector.copy()
        matrixToFillWithOne.append(1)
        matrixToFillWithZero.append(0)
        matrix(length,matrixToFillWithOne,fullMatrix)
        matrix(length,matrixToFillWithZero,fullMatrix)
    
    else:
        fullMatrix.append(combinationVector)
        fullMatrix.sort()
    return fullMatrix


if __name__ == '__main__':
    matrix(3, [],[])

Pasaremos tres elementos, los cuales serán:

fullMatrix-> La matriz final que llenaremos con todas las combinaciones.

combinationVector -> Una de las posibles combinaciones [0,0,0][0,1,0].....

length-> Tamaño que queremos.

El funcionamiento es sencillo así que creo que con un esquema quedará más claro tras leer el código:

                                  []
                                /    \
                              [0]     [1]
                              / \     / \
                          [0,0] [0,1] [1,0] [1,1]

Así se irán extendiendo en árbol todas las posibles combinaciones. Una vez la tengamos, la añadiremos a fullMatrix donde serán ordenadas, siendo el resultado final:

[[0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 1, 1], [0, 1, 0, 0], [0, 1, 0, 1], [0, 1, 1, 0], [0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 1], [1, 0, 1, 0], [1, 0, 1, 1], [1, 1, 0, 0], [1, 1, 0, 1], [1, 1, 1, 0], [1, 1, 1, 1]]
2

Ya que se trataba de un ejercicio de clase, no quería darte la respuesta sin antes dejarte que lo intentaras por tí mismo. Pero puesto que finalmente te han dado una respuesta y la has aceptado, me veo forzado a intevenir.

La respuesta aceptada, aunque usa recursión en un sentido literal (pues la función matrix() contiene llamadas a sí misma), no la está usando en la forma correcta. Tal como está implementado, esa recursión no es más que un mecanismo para añadir n unos o n ceros a una lista. Perfectamente reemplazable por un bucle que se repita n veces.

La gracia de la resursividad es que la implementación resuelva un problema de forma recursiva, es decir, basándose en la solución a un problema más pequeño. Déjame explicarme.

Planteamiento

  • Queremos resolver el problema de encontrar una lista con todas las combinaciones posibles de N bits.
  • La idea "recursiva" es: imagina que tienes una función que te resuelve el caso N-1 . Por ejemplo llamemos f() a esa función e imaginamos que cuando la invocas, es capaz de darte todas las combinaciones posibles de N-1 bits_.

    Es decir, supón que N es 3, y que entonces puedes llamar a f(2) y te devuelve la lista [[0,0], [0,1], [1,0], [1,1]]. La pregunta és ¿Cómo usaríamos esa función como parte de nuestra solución para N?

    Piénsalo un ratito y sigue leyendo.

Una vez tengamos la idea, immplementaremos una solución que use f(N-1) como base para construir la solución para N:

  • Escribe un caso trivial que se resuelva "directamente" (es decir, sin necesidad de llamar a f()). Este caso trivial se usará si N es 0.
  • Escribe como resolver el caso para otro N, usando el resultado devuelto por f(N-1).

La cosa sería así (pseudocódigo):

  1. Si N==0 retornar la lista [[]]. Este es el caso trivial que podemos resolver sin necesidad de usar f(). Es una lista que tiene un solo elemento, la lista vacía. Ya que con N igual a 0 bits, esa es la única combinación que podemos formar (el conjunto vacío).
  2. En otro caso tenemos que apoyarnos en el resultado devuelto por f(N-1). Podemos hacerlo así.

    • Prepara una lista vacía para el resultado a devolver: resultado = [] Esa lista al final tendrá todas las combinaciones de N bits buscadas.
    • Usa f(N-1) para obtener la lista de combinaciones de N-1 bits, o sea: sol = f(N-1)

      Cada elemento de la lista sol será una combinación diferente de N-1 bits, basta añadirle el bit que falta (que dará dos posibilidades más), así que:

    • Para cada elemento de sol, añade a resultado la lista elemento + [0] y la lista elemento + [1]
    • retorna la lista resultado

Ejemplo para ver cómo funciona

Vamos a comprobar que funciona para N=3. Al llamar a f(2) tendríamos en sol la lista [[0,0], [0,1], [1,0], [1,1]]. Así que al iterar por esta lista:

  • El primer elemento es [0,0], con lo que añadimos a resultado las listas resultantes de concatenarle al final un 0 y un 1, por tanto las listas [0,0,0] y [0,0,1]
  • El segundo elemento es [0,1], lo que añadirá a resultado las listas [0,1,0] y [0,1,1]
  • etc.. ¿ves cómo se van formando combinaciones válidas en resultado?

Pero...

Ahora queda un importante detalle. Dirás "todo esto está muy bien, pero estoy presuponiendo que tengo una función f() capaz de resolverme el caso N-1... ¿de dónde saco esa función?

Y aquí está la magia de la recursividad. ¡Resulta que esa función acabamos de escribirla! ¡Es la misma función que calcula el caso f(N)! Basta por tanto que se llame a sí misma cuando necesite la solución para f(N-1).

Creo que con esto tienes los ingredientes teóricos necesarios para poder codificar en python una solución correcta al problema que te han planteado.

6
  • Sí, el código es remplazable por una definición iterativa, pero de la manera que está hecho y según mis cálculos, hacer estos problemas de manera recursiva ahorra coste computacional y por ello se hace así. No entiendo bien que quiere decir con que se usa de forma correcta.¿Podría aclararlo?
    – Yeste
    Commented el 14 oct. 2019 a las 16:10
  • @Yeste El enfoque recursivo nunca ahorra ni tiempo de ejecución ni recursos de almacenamiento. Siempre requiere más memoria (porque los marcos de pila de las sucesivas llamadas deben ser almacenados) y más tiempo de ejecución (porque la propia llamada es una sobrecarga debido a la necesidad de apilar los parámetros y la dirección de retorno). La única ventaja que tiene una implementación recursiva es que el código suele ser mucho más compacto y fácil de comprender (si se comprende el concepto de recursividad). Si se desea optimizar el código es mejor abandonar la recursividad ...(sigue)
    – abulafia
    Commented el 14 oct. 2019 a las 16:25
  • ...(sigue) e implementarlo de forma iterativa, es decir, con un bucle. En tu caso, tu solución utiliza la recursividad en un punto en que no mejora la legibilidad, pues un bucle for sería más legible. No obstante, ya que al usuario que hizo la pregunta le "obligan" a usar recursividad, técnicamente tu respuesta sería válida, pues la está usando. Mi juicio de que no es la forma "correcta" se refiere a que la forma en que lo usa tu solución no es en base al "método inductivo", es decir, aquel por el que se parte de la hipótesis de que se tiene resuelto para el caso N-1 y ...(sigue2)
    – abulafia
    Commented el 14 oct. 2019 a las 16:28
  • ...(sigue2) y se usa esa solución previa para "aumentarla" y así obtener la solución para el caso N. Es este principio "inductivo" el que suele lograr que una implementación recursiva sea más sencilla conceptualmente que una solución iterativa, y no posibles consideraciones sobre eficiencia ya que, como dije antes, en este aspecto la implementación recursiva es peor. Tu solución carecía de este aspecto "inductivo" y por eso la consideré menos "correcta".
    – abulafia
    Commented el 14 oct. 2019 a las 16:29
  • Muy interesante y muy bien explicado, gracias por la aclaración, +1!
    – Yeste
    Commented el 14 oct. 2019 a las 17:07

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.