estoy tratando con el siguiente problema:
Dada una matriz, por ejemplo:
array = [[7, 3, 7, 2],
[9, 9, 4, 1],
[9, 4, 8, 1],
[3, 4, 8, 4]]
Quiero seleccionar de cada fila, el menor número, de forma que no pueda seleccionar dos números de filas distintas que estén en la misma columna. Por ejemplo, en este caso, al seleccionar de la primera fila el 2, en la segunda fila ya no podría seleccionar el 1 , ya que coinciden las columnas.
Una idea de algoritmo que he pensando es la siguiente:
- Miro la primera fila y cojo el menor número.
- Miro la segunda fila y cojo el más bajo. Si este coincide con la columna escogida anteriormente, cojo el segundo más bajo.
- Así hasta que acabo de recorrer todas las filas de la matriz.
Tengo esta idea pero no consigo implementarla, si alguien pudiese ayudarme.
Edición:
Alguien me ha aconsejado partir de la idea más básica, que sería guardar el mínimo de cada fila sin importar la condición de la columna:
lis = []
p = []
for fila in array:
a = fila.index(min(fila))
if a not in p:
lis.append(fila[a])
p.append(a)
else:
print(fila)
Con a, encuentro el índice del número más pequeño de una fila. Añado este índice en un vector en el que guardo posiciones y añado en otra lista el valor de este número.
Después, compruebo si en el vector de posiciones está el siguiente índice del número más pequeño. Esto es una forma de comprobar que no está escogiendo la misma columna.
Ahora, si se cumple esta condición, no se como seleccionar el mínimo de esa fila excluyendo el valor en la posición repetida.