Compendio de Algoritmos [ENG]

Compendio de algoritmos ( ~500 ) ordenados por temas, con explicación y código en C / Java: Arrays, matrices, árboles, grafos, backtrack, cadenas, ordear, pilas, colas, puzzles...

[#1 filtrodelapradera]

He revisado unos pocos. Más que algoritmos, son implementaciones de algoritmos.
Muy recomendable.

[#4 Desactivado]

Además en C++. Esta cada día más complicado el ver algoritmos que no estén hechos en Python.

#1 esto es mucho más valioso.

[#7 filtrodelapradera]

#4 Esta cada día más complicado el ver algoritmos que no estén hechos en Python.

Precisamente ahí está el valor de los algoritmos. Te cuentan el meollo del problema y una forma abstracta de solucionarlo. Y luego coges una implementación en el lenguaje que quieras/puedas/te pidan/etc. en caso de que la haya. Y si no la hay, tienes una base para hacértela.

De todas formas, no era una queja. A caballo regalado...

[#9 Desactivado]

#7 No si lo entiendo, el problema es que en teoría es así y en la práctica el 90% se pierde si lo sacas de un lenguaje de script.

Vamos que si no eres capaz de sacar el pseudocódigo a partir de un código completo, no esperes ser capaz de hacerlo al revés.

[#18 pom]

#9 como comento en #15, Python tiene la sencillez de muchos pseudocodigos de libro.

Lo importante es que quede claro el algoritmo. Si usas un "for each", obviamente necesitas saber si tu lenguaje lo tiene o no y en el peor de los casos como implementarlo.

Si no eres capaz es porque: no tienes conocimiento suficiente de tu lenguaje, o bien porque el ejemplo que te han puesto está muy atado a librerías específicas (lo cual, significa que el ejemplo intenta mostrarte otra cosa). También existe la posibilidad de que el ejemplo sea muy enrevesado.

[#21 Desactivado]

#18 Hay una clara diferencia entre lenguajes de script y los que no lo son. Si aprendes en Python no estás capacitado para escribir en otros lenguajes.

[#23 pom]

#21 ese comentario está a la altura de la típica frase "un desarrollador de front no es un programador de verdad". Que sepas que Python y C van muy de la manita.

En fin, deduzco de tu comentario que la mejor curva de aprendizaje es ASM, C, C++, Java/.NET y luego ya si eso chuminadas estilo Python/Javascript, y que paradigmas funcionales estilo Haskell o logicos estilo Prolog no valen la pena .

Los algoritmos son independientes del lenguaje y la complejidad de ellos es medible. Cuando estudias algoritmos se suele recurrir a programación funcional (reduce, filter, maps,...), habitualmente usada en pseudocodigo.

Te cambio tu frase a "si no conoces los distintos paradigmas de programación, no estás capacitado para entender las implementaciones de los algoritmos". De la misma forma, si no entiendes de notación matemática, difícilmente entenderás las formulaciones hechas en papers estilo IEEE.

[#29 Desactivado]

#23 #24 Es que yo no he dicho lo contrario, he dicho que tampoco es suficiente con ello (que es distinto).

Ahora trabajo con Unreal Engine y no hay nada peor que un programador "experimentado" que se cree que lo va a dominar en 4 días porque el lo vale (y luego llega la ostia y los lloros).

[#15 pom]

#4 no entiendo el problema de que estuviesen en otro lenguaje. Como ejemplos de implementación de algoritmos, lo importante es qie te dejen claro como funcionan (portarlos a otro lenguaje debería ser trivial).

Lo bueno de Python es que tiene la sencillez del pseudocodigo, e incluso puedes probar directamente en el interprete o en notebooks Jupyter o similares (personalmente creo qur resulta más didactico).

[#20 Desactivado]

#15 El problema es que hay toda una generación de "programadores" que no sabe hacer otra cosa y para los cuales "portar" a otros lenguajes no es trivial. Pero te asegurarán que son perfectamente capaces (si les das un par de años más, claro).

[#24 pom]

#20 insisto, hablamos de algoritmos. Lo importante es que lo entiendas.

Puedes implementarlo de forma más o menos eficiente, pero si tienes que implementar un Backtracking, el algoritmo de Dijkstra,... lo tienes que entender, no dedicarte a traducir de un lenguaje a otro como monos sin cabeza.

Pero claro, hoy dia lo fácil es "stackoverflow + control C + control V", y esperar tener que hacer poco más.

[#28 EspañoI]

#4 si trajeran C(n), O(n) ya calculados serían perfectos para llevar rodada media carrera

[#27 alexwing]

Recuerdo hace tiempo como 2003, o por ahi, necesitaba pasar el algoritmo que calcula MD5 que había pillado para visual basic a PHP, conseguí migrarlo y hacerlo funcionar, justo cuanto termino descubro que ya existía en PHP como funcion nativa.

[#31 fperez]

Hay una persona en Menéame que está muy en contra de los algoritmos. Que raro.

[#19 slow_biker]

después de 40 años programando he aprendido hace poco la forma correcta y precisa de sumar los elementos de un vector, Kahan hizo el milagro. https://github.com/rforcen/Vect

[#37 woopi]

#36 Sector de algoritmia, complejidad y acotando un poco, el problema de las n reinas.

[#2 scalvo]

Ya que estamos, poca gente me leerá, pero lo pregunto. Tengo el siguiente problema, y me gustaría saber si hay un algoritmo eficiente que pueda usar:

Tengo una lista de tuplas que relaciona posiciones de índices: list = [(0,1), (1,2), (2, 3).....(n-1, n)].

Los datos representados por los índices pueden ser borrados, por ejemplo, en list[1] podríamos borrar el elemento que señala "2", de forma que queda así [(0, 1), (1, 3), (2, 4).....(n-2, n)].

Lo que me gustaría es saber qué algoritmo es eficiente para tratar "remapeos" de listas de tuplas. Siempre habrá una relación similar en cuando se eliminen elementos. Puedo programarlo fácilmente, sin problema, reescribiendo toda la lista. La lista más larga posible tendrá, como mucho, 7 u 8 mil elementos....

Pero me gustaría conocer alguna forma eficiente para listas mucho más grandes.

Una solución que se me ocurre es olvidarme de la lista, y buscar una forma de hacerlo puramente funcional, de forma que no exista la lista, sino que sólo exista una función de mapeo... pero eso (que sin duda es lo más eficiente) es demasiado complejo para mi cabeza.

[#3 Barquero_]

#2 No has borrado el elemento que "señala a" sino el elemento "señalado"
¿algo así?
a1 = ['0','1','2','3','4']
a2 = ['1','2','3','4','5']
i=0
while i < len(a2):
print a1[i] + ' apunta a: ' + a2[i]
i=i+1
print 'eliminar un elemento'
del a2[2]
i=0
while i < len(a2):
print a1[i] + ' apunta a: ' + a2[i]
i=i+1

$python main.py
0 apunta a: 1
1 apunta a: 2
2 apunta a: 3
3 apunta a: 4
4 apunta a: 5
eliminar unelemento
0 apunta a: 1
1 apunta a: 2
2 apunta a: 4
3 apunta a: 5

[#8 Desactivado]

#3 Creo que #2 se refiere a una forma de evitar la "reasignación" de elementos producida en el array a partir de i+1 cada vez que se elimina un elemento i.

[#10 Sr.No]

#8 punteros dinamicos?

[#13 Desactivado]

#11 El tema es que casi todo son "algoritmos conocidos", incluso los problemas reales. Los algoritmos son patrones que se aprende a aplicar a esos problemas.

#10 Yo solo añadiría otro Array (o hashmap) con booleanos que simplemente indicase si esa entrada es válida o no, así no hay que reescribir nada.

[#17 scalvo]

#8 Exacto. Eso es.

[#22 Desactivado]

#17 Básicamente haría como #3, pero el primer Array es innecesario. Siempre va a ser un contador de 0 a N.

Podemos tener un Array para el mapeo inicial, y otro con bools que indique si el valor correspondiente del primer Array es válido o no.

El output puede darse haciendo un loop en el Array original con la ayuda un segundo contador/puntero que recorra el array de bools ignorando los false.

[#25 perrico]

#2 #3 idos a un hotel.
O a stackoverflow.

[#32 Desactivado]

#3 ostias. Así si

[#33 pawer13]

#2 Pon una pregunta en Stack Overflow. Hay versión en español, si tienes problemas con el inglés

[#34 EspañoI]

#2 regenerar los indices es muy ineficiente, y va a acabar dando al traste con tu codigo en cuanto modifiques el algoritmo.

Por mi experiencia personal, yo incluiria un tercer parametro, un flag de 1 bit para saber si la entrada esta activa o no:
list = [(0,1,1), (1,2,0), (2, 3,1).....(n-1, n,bool)].

De esta manera, solo incrementas el tamaño de la tupla en un bit, y solo debes añadir a tu codigo la condición de valor válido.
Del mismo modo, si modificas un elemento de tu tupla, basta con desactivar la anterior, y copiar la nueva version al final.

Posteriormente una rutina de mantenimiento podría eliminar las entradas no validas.

[#5 eldet]

Para las preguntas de entrevista.
Hazme un tal con tal: Pues lo busco en la pagina

[#6 Desactivado]

#5 La verdad es que me hubiese venido bien hace unas semanas. Las páginas que ofrecen algo parecido cuestan cientos de euros.

[#11 Desactivado]

#5 nunca he entendido el propósito de pedir implementar un algoritmo conocido. Me parece más útil plantear un problema real y preguntar por soluciones. De qué me sirve memorizar el problema de las nueve reinas?

[#12 aavvaallooss]

#11 No eran 8?

[#14 woopi]

#12 De hecho, el problema gordo es el de las n reinas.

[#30 redjhawk]

#14 ¿Y la paridad?

[#35 woopi]

#30 No sé. ¿Alguna pista?

[#36 redjhawk]

#35 Depende. ¿De qué sector estamos hablando?

[#16 slow_biker]

#11 https://github.com/rforcen/queens
Qt / mutithread

[#26 eldelshell]

#11 ya, yo creo que sería más útil patrones, que sí es algo que se usa casi a diario, cuando nadie implementa un BST después de salir de la facultad.