arrejuntando listas

Published 19/9/2007 12:15

Antes de que nadie me comente nada: prometo que "arrejuntarse" es un verbo español perfectamente valido! Pese a que suene un poco "brutito" en realidad se refiere a vivir vida de casados sin estarlo. Tengo de hecho un par de amigos que estaban haciendo eso mismo hasta que hace unos meses se les fue la pinza cambiaron de idea y decidieron casarse, asi que este finde nos tocara boda! (y vistos los ejemplos de algunos miembros de geeks, parece que este año hay ida de olla general tendencia al tema)

Pero en fin, nosotros a lo que es el codigo, que es lo nuestro...

 

 Vamos a proponer hoy un par de variaciones de problemas con listas:

Para empezar, imaginemos que tenemos dos listas previamente ordenadas y que queremos generar una tercera lista que tenga todos los elementos de las dos anteriores, pero tambien ordenados. Asi por ejemplo si una lista es (1,4,7) y la otra (2,5,6) el resultado debe ser la lista (1,2,4,5,6,7)

Podrias escribir una funcion que reciba como entrada las dos listas y que devuelva la lista resultante, segun la descripcion anterior? Se te ocurre una forma de crear una funcion generalizada que haga lo mismo para un numero N de listas?

Y ahora imaginemos que tenemos un sentido del orden un poco extraño, y que lo que queremos es ordenar las listas de modo que en la lista resultado los elementos impares esten ordenados ascendentemente partiendo desde el centro y hacia la izquierda, y los pares desde el centro, hacia la derecha. Es decir, en el ejemplo anterior con (1,4,7) y (2,5,6) nuestro resultado deberia ser (7,5,1,2,4,6)

Podrias escribir una funcion que cree la lista resultante en este caso?

por phobeo
Archivado en: ,,
Comparte este post:

Comentarios

# Lucas Ontivero said on Wednesday, September 19, 2007 2:48 PM

A menos que exista un algoritmo algo medio sorprendente para resolver el primer problema, yo haria lo siguiente:

- creo una lista de tamaño list1.Lenght + list2.Lenght

- recorro con un mismo indice las dos listas simultaneamente y pregunto: es list1Idea > list2Idea y si es as'i inserto primero list2Idea en la nueva lista y luego inserto list1Idea de lo contrario inserto en orden inverso, primero list1Idea y luego list2Idea. Existe un problemita con que las listas no tienen por que ser de igual tamaño as'i que hay que controlar eso.

Es así? :)

El segundo problema lo voy a pensar porque ac'a ya me estan mirando raro.

# phobeo said on Wednesday, September 19, 2007 3:42 PM

buenas, Lucas: la solucion puede funcionar pero... no siempre se inserta en ese orden, no?

Puedes probar tu algoritmo con, por ejemplo las listas (1,2,3,4,5) y (6,7,8,9)... funcionaria?

# kaken said on Wednesday, September 19, 2007 6:13 PM

Hello, si se puede usar las caracterisiticas del framework yo haria esto(por cierto es lo primero q se me ha ocurrid).

Public Sub OrdenarListas(ByVal lista1() As String, ByVal lista2() As String)

       Dim ntotal As Integer = (lista1.Length + lista2.Length) - 1

       Dim listatotal(ntotal) As String

       lista1.CopyTo(listatotal, 0)

       lista2.CopyTo(listatotal, lista1.Length)

       Array.Sort(listatotal)

   End Sub

# Carlos Durbán said on Wednesday, September 19, 2007 6:15 PM

   Public Sub OrdenarListas(ByVal lista1() As String, ByVal lista2() As String)

       Dim ntotal As Integer = (lista1.Length + lista2.Length) - 1

       Dim listatotal(ntotal) As String

       lista1.CopyTo(listatotal, 0)

       lista2.CopyTo(listatotal, lista1.Length)

       Array.Sort(listatotal)

   End Sub

# Carlos Durbán said on Wednesday, September 19, 2007 6:21 PM

Sorry por las trampas :)

# Rosita Fraguel said on Wednesday, September 19, 2007 6:38 PM

Voy a dar mi respuesta a la primera (primerísima) pregunta. No sé si se me ha pasado algo por alto, lo que sí tengo que confesar es que me lo he pasado pipa dándole vueltas a esto. (Espero que eso no signifique que estoy echando de menos programar)

Cosas que he supuesto:

-que existe una función mágica que te dice la longitud de las listas

-que puede haber elementos repetidos entre las listas

int []lista1;

int []lista2;

int []lista3;

int lista1_length=lista1.length();

int lista2_length=lista2.length();

int i=0;

int j=0;

int k=0;

while (i!=(lista1_length-1) || j!=(lista2_length-1)){

               if(lista1Idea<lista2[j]){

                       lista3[k]=lista1Idea;

                       k++;

                       if(i!=lista1_length-1)i++;

               }else if(lista1Idea>lista2[j]){

                       lista3[k]=lista2[j];

                       k++;

                       if(j!=lista2_length-1)j++;

               }else{

                       lista3[k]=lista1Idea;

                       k++;

                       if(i!=lista1_length-1)i++;

                       if(j!=lista2_length-1)j++;

               }

}

# Rafael Vargas said on Wednesday, September 19, 2007 7:22 PM

Este es el típico problemita de "Tech Interview". Perfecto para hacerlo en C/C++.

Problema 1:

Yo recorrería con dos punteros cada lista e iría avanzando según se inserta de una y de otra y hasta que el número de elementos insertados no fuera igual a la suma de ambas listas. Si evidentemente se llega al final de una antes que al de otra, entonces rellenaría el resto con el final de la otra.

Problema 2:

Pues más o menos sería seguír con la misma idea, pero en este caso, tendríamos un ArrayNo de punteros hacia elementos de las N-listas.

Antes de cada inserción, se recorrería el último elemento apuntado de cada lista, se compararía y se tomaría el menor, avanzándolo una posición. Así, hasta que sólo queden dos listas.

También cabe la posibilidad de unir las N-listas dos-a-dos con el sistema anterior, ya que para una entrada del tipo que comentas: "Puedes probar tu algoritmo con, por ejemplo las listas (1,2,3,4,5) y (6,7,8,9)... funcionaria?" ganaríamos en eficiencia.

Ahí van mis dos céntimos.

# phobeo said on Wednesday, September 19, 2007 8:48 PM

buenas crases,

kaken, carlos: bueno, es una solucion valida (excepto en un caso, aunque eso lo dejamos para nota) pero hay un par de cosas que podriamos cambiar... mirando el tema de la eficiencia, por ejemplo, realizas 2 CopyTo y un Sort. Cada CopyTo es de orden n, y el Sort en .NET utiliza Quicksort, que es en promedio de orden n*log(n), asi que estamos en un total de n+n+n*log(n). El metodo de ir recorriendo los arrays como apunta por ejemplo Rosita, es de orden n+n... mucho mas mejor, no?

Por apuntar una cosa mas (por si alguien es curioso y le interesa mirar detalles del tema), el Quicksort realiza una ordenacion de las denominadas "inestables" (que quiere decir que los elementos de valor igual en la entrada pueden cambiar de orden en la salida) Esto no tiene importancia en los supuestos de que las listas sean de elementos por valor (como es el caso de las listas de enteros que ha supuesto Rosita) PERO puede ser relevante en el caso de que lo que tengamos en la lista sean referencias (recordemos que Sort usa la interfaz IComparable, que segun la implementacion puede hacer que referencias distintas se comparen como iguales)

NOTA: para Java, cambiese IComparable por Comparable y Sort por Collections.sort o Arrays.sort, para C++ con STL, cambiese por operator< y sort()... pero el caso es que puede pasar lo mismo en cualquiera de estos lenguajes

Rosita: me alegro que te gustara el problemilla... ahora te tienes que animar con el segundo! }:D

Por cierto, que es lo que hace el caso "else" en tu codigo? No podrias simplemente incluirlo en uno de los otros (recuerda que en el resultado queremos TODOS los elementos de las listas... incluyendo duplicados)

Vargas: Efectivamente, es un problema que se suele utilizar para despues evolucionar a una discusion sobre cierto algoritmo de ordenacion };D

Aqui lo he cambiado un poco porque me interesaba discutir de otras cosas, incluyendo el que hay detalles que no son tan simples como parecen. Por ejemplo, las tres soluciones que estoy comentando ahora mismo tienen un fallito que hace que haya casos en los que no funcionen... se os ocurre en cual?

Pista: es un problemilla que no ocurre ni en tu solucion ni en la de Lucas porque habeis usado lenguaje natural, en vez de codigo como los valientes! };D

# Rafael Vargas said on Wednesday, September 19, 2007 9:44 PM

En caso de que una(o ambas) de las listas esté vacía, las soluciones fallarían. No se contempla ese tipo de casos.

# Lucas Ontivero said on Wednesday, September 19, 2007 9:52 PM

Eso me pasa por hacerme el rápido! No, no funciona ni a palos. Esta noche me pongo y lo saco. Estoy como el Doctor alemán de "La vida es bella" y no voy a poder dormir si no lo resuelvo pronto.

# Rosita Fraguel said on Wednesday, September 19, 2007 10:01 PM

Bueno, veo que he hecho varias suposiciones muy supuestas :P

Pues sí que me he animado, me pasaré por aquí más a menudo antes de que se muera la neurona que me queda jiji

Mañana si no estoy tan cansada como hoy me pongo a pensar el resto.

Buenas noches a todos zzzzzzzZZZZZZZZZZ

# phobeo said on Wednesday, September 19, 2007 10:03 PM

Lucas: me vas a obligar a poner un banner de "las autoridades advierten que programancia101 perjudica seriamente sus horas de sueño"? };D

Me alegro que "te piques" un poco, de todas formas... vas bien! solo hay que cambiar alguna cosilla...

Vargas: es una posibilidad, pero si las listas estan vacias, mientras que las funciones de longitud devuelvan cero, seguirian funcionando

Pista: Que pasaria si en vez de vacias estuvieran llenas?

# Tio_Luiso said on Thursday, September 20, 2007 9:18 AM

Muy buenas caballero. El primer problema lo resuelvo con un MergeSort. Sería muy similar para n listas. He intentado hacer alguna tontería con generics. El resultado es este:

   class MergeSort<T> where T : IComparable

   {

       public static List<T> Sort(List<T> list1, List<T> list2)

       {

           List<T> destinationList = new List<T>();

           while (list1.Count > 0 || list2.Count > 0)

           {

               if (list1.Count == 0 || list2[0].CompareTo(list1[0])<0)

               {

                   destinationList.Add(list2[0]);

                   list2.RemoveAt(0);

               }

               else

               {

                   destinationList.Add(list1[0]);

                   list1.RemoveAt(0);

               }

           }

           return destinationList;

       }

   }

Ahora pensaré en el 2º problema

# Rosita Fraguel said on Thursday, September 20, 2007 12:17 PM

Si la mezcla la hago para un número n de listas sólo se me ocurre un algoritmo de orden n^2... ¿se puede hacer más baja la complejidad?

# phobeo said on Thursday, September 20, 2007 12:59 PM

hola crases!

Rosita: Mmm... dependiendo de como lo codifiques... si, se puede

Pista: mirate el grafiquito de la derecha de este articulo de wikipedia: en.wikipedia.org/.../Mergesort

Tio_Luiso: ya te echaba de menos! }:D

Efectivamente, de eso va el asunto. Muy bueno lo de hacerlo con Generics para evitar presuposiciones (aunque ya sabes que se permite).  

Solo un pequeño detalle: que pasa si pruebas tu algoritmo con las listas (1,2,3) y (), por ejemplo?

(ah! y espero que te animes con el segundo tambien!)

# Tio_Luiso said on Thursday, September 20, 2007 2:46 PM

Right you are. Es mejor algo asín:

public static List<T> Sort(List<T> list1, List<T> list2)

       {

           List<T> destinationList = new List<T>();

           while (list1.Count > 0 || list2.Count > 0)

           {

               List<T> sourceList = null;

               if (list1.Count == 0)

               {

                   sourceList = list2;

               }

               else if (list2.Count == 0)

               {

                   sourceList = list1;

               }

               else if (list2[0].CompareTo(list1[0]) < 0)

               {

                   sourceList = list2;

               }

               else

               {

                   sourceList = list1;

               }

               destinationList.Add(sourceList[0]);

               sourceList.RemoveAt(0);

           }

           return destinationList;

       }

# Tio_Luiso said on Friday, September 21, 2007 12:40 PM

Por lo que veo, para la resolución del 2º problema no se mantiene la premisa de que las dos listas estén previamente ordenadas (ni de forma natural ni de ninguna otra forma).

Lo que hago es:

1.- Crear una lista de enteros (en este caso no le encuentro sentido a los genéricos)

2.- Añadirle los elementos de la lista1

3.- Añadirle los elementos de la lista2

4.- Invocar el método Sort pasándole una instancia de un IComparer<int> tal que el que me he creado:

public class ProgramanciaComparer : IComparer<int>

   {

       #region IComparer<int> Members

       public int Compare(int x, int y)

       {

           if (x % 2 == 1 && y % 2 == 0)

           {

               // x impar, y par, x menor que y

               return -1;

           }

           else if (y % 2 == 1 && x % 2 == 0)

           {

               // x par, y impar, y menor que x

               return 1;

           }

           else if (x % 2 == 0)

           {

               // x e y pares. orden normal

               return x.CompareTo(y);

           }

           else

           {

               // x e y impares. orden inverso

               return -(x.CompareTo(y));

           }

       }

       #endregion

   }

Me figuro que habrá formas mucho mejores, pero ahora no se me ocurren. Esta funciona. Eso lo he comprobado.

¿Cuál es tu solución?