Hola gente!
Algo mas matematico, con tests, y usando dos generadores para obtener todas las permutaciones: http://msmvps.com/blogs/lopez/archive/2011/01/04/permutations_2D00_in_2D00_a jgroups.aspx Angel AjGroups Lopez From: [email protected] [mailto:[email protected]] On Behalf Of Agustin Calcagno Sent: Thursday, September 15, 2011 2:13 AM To: [email protected] Subject: [puntonet] Algoritmo para permutaciones Por ahí te sirve también esta solución. Que es un poco más orientada a objetos, con todo lo que ello implica. Tiene los tests, y dos clases. [TestClass] public class UnitTest1 { [TestMethod] public void deberia_poder_permutar_dos_valores_de_una_digito() { Permutador una_permutacion = new Permutador(); var AB = new Digito(new List<string>(new string[] { "A", "B" })); var digitos = new List<Digito>() { AB }; var permutaciones = una_permutacion.GetPermutaciones(digitos); Assert.AreEqual(2, permutaciones.Count()); Assert.IsTrue(permutaciones.Contains("A")); Assert.IsTrue(permutaciones.Contains("B")); } [TestMethod] public void deberia_poder_permutar_dos_unidades_permutadoras_de_un_valor() { Permutador una_permutacion = new Permutador(); var A = new Digito(new List<string>(new string[] { "A" })); var B = new Digito(new List<string>(new string[] { "B" })); var digitos = new List<Digito>() { A, B }; var permutaciones = una_permutacion.GetPermutaciones (digitos); Assert.AreEqual(1, permutaciones.Count()); Assert.IsTrue(permutaciones.Contains("AB")); } [TestMethod] public void deberia_poder_permutar_dos_unidades_permutadoras_de_dos_valoes_sin_repetidos () { Permutador una_permutacion = new Permutador(); var XZ = new Digito(new List<string>(new string[] { "X", "Z" })); var digitos = new List<Digito>() { XZ, XZ }; var permutaciones = una_permutacion.GetPermutaciones(digitos); Assert.AreEqual(2, permutaciones.Count()); Assert.IsTrue(permutaciones.Contains("XZ")); Assert.IsTrue(permutaciones.Contains("ZX")); Assert.IsFalse(permutaciones.Contains("XX")); Assert.IsFalse(permutaciones.Contains("ZZ")); } [TestMethod] public void deberia_poder_permutar_varias_unidades_permutadoras_de_varios_valoes_sin_rep etidos() { Permutador una_permutacion = new Permutador(); var ABCD = new Digito(new List<string>(new string[] { "A", "B", "C", "D" })); var digitos = new List<Digito>() { ABCD, ABCD, ABCD, ABCD }; var permutaciones = una_permutacion.GetPermutaciones(digitos); Assert.AreEqual(24, permutaciones.Count()); Assert.IsTrue(permutaciones.Contains("ABCD")); Assert.IsTrue(permutaciones.Contains("ABDC")); Assert.IsTrue(permutaciones.Contains("ACBD")); Assert.IsTrue(permutaciones.Contains("ACDB")); Assert.IsTrue(permutaciones.Contains("ADBC")); Assert.IsTrue(permutaciones.Contains("ADCB")); Assert.IsTrue(permutaciones.Contains("BACD")); Assert.IsTrue(permutaciones.Contains("BADC")); Assert.IsTrue(permutaciones.Contains("BCAD")); Assert.IsTrue(permutaciones.Contains("BCDA")); Assert.IsTrue(permutaciones.Contains("BDAC")); Assert.IsTrue(permutaciones.Contains("BDCA")); Assert.IsTrue(permutaciones.Contains("CABD")); Assert.IsTrue(permutaciones.Contains("CADB")); Assert.IsTrue(permutaciones.Contains("CBAD")); Assert.IsTrue(permutaciones.Contains("CBDA")); Assert.IsTrue(permutaciones.Contains("CDAB")); Assert.IsTrue(permutaciones.Contains("CDBA")); Assert.IsTrue(permutaciones.Contains("DABC")); Assert.IsTrue(permutaciones.Contains("DACB")); Assert.IsTrue(permutaciones.Contains("DBAC")); Assert.IsTrue(permutaciones.Contains("DBCA")); Assert.IsTrue(permutaciones.Contains("DCAB")); Assert.IsTrue(permutaciones.Contains("DCBA")); } } class Digito { /* * Esta clase representa un elemento de una permutacion * que puede tener n valores * por ejemplo los numeros tienen n = 9 * pues los valores son 0,1,2,3,....9 * */ List<string> valores; public Digito(List<string> valores) { this.valores = valores; } internal List<String> GetValuesNoContenidosEn(string perm) { return valores.FindAll(val => !perm.Contains(val)); } } class Permutador { public List<string> GetPermutaciones(List<Digito> digitos) { return Filtrar(conjunto:GetCombinacionesDe(digitos), por_longitud: digitos.Count); } public List<string> GetCombinacionesDe(List<Digito> digitos) { return GetResultado(de_aplicar_la_funcion: (resultado) => digitos.ForEach(u => resultado.AddRange(this.Combinar(digito: u, con: resultado))) ); } /// <summary> /// Realiza el producto cartesiano entre los valores de un digito, y los strings de un conjunto dado /// </summary> /// <param name="digito">digito cuyos valores se desean combinar</param> /// <param name="con">conjunto de strings que se desea combinar</param> /// <returns>conjunto de (digito x con) strings, combinatoria de ambos</returns> private List<string> Combinar(Digito digito, List<string> con) { return GetResultado(de_aplicar_la_funcion: (resultado) => con.ForEach(perm => digito.GetValuesNoContenidosEn(perm).ForEach(value => resultado.Add(perm + value))) ); } /// <summary> /// Quita los elementos que no cumplan la condicion de tener una longitud dada /// </summary> /// <param name="conjunto">conjunto de strings que se desean filtrar</param> /// <param name="por_longitud">longitud de los strings deseados</param> /// <returns>conjunto con strings del tamaño deseado</returns> private List<string> Filtrar(List<string> conjunto, int por_longitud) { return conjunto.FindAll(elemento => elemento.Length == por_longitud); } /// <summary> /// Idiom que crea un conjunto de resultados de evaluar una funcion /// </summary> /// <param name="de_aplicar_la_funcion">funcion que recibe un conjunto de strings donde se guardaran los resultados de su evaluacion</param> /// <returns>conjunto de resultados de evaluar la funcion</returns> private List<string> GetResultado(Action<List<string>> de_aplicar_la_funcion) { var resultado = new List<string>(new string[] { "" }); de_aplicar_la_funcion(resultado); return resultado; } } El 14 de septiembre de 2011 18:19, Tomás Corrales Lemoine <[email protected]> escribió: Un millón de gracias, José, es lo que necesitaba. Saludos, Ing. Tomás Corrales Lemoine De: [email protected] [mailto:[email protected]] En nombre de Jose Selesan Enviado el: Miércoles, 14 de Septiembre de 2011 02:49 p.m. Para: [email protected] Asunto: [puntonet] Algoritmo para permutaciones Hola Tomás. Con una simple recursividad lo podés resolver: private IEnumerable<string> Permutaciones(IEnumerable<string> lista) { if (lista.Count() == 1) return lista; var resultado = new List<string>(); foreach (var elemento in lista) { var listaPermutada = Permutaciones(lista.Where(t => !t.Equals(elemento))); foreach(var permutacion in listaPermutada) resultado.Add(elemento + permutacion); } return resultado; } Saludos Lic. José Selesan 2011/9/14 Tomás Corrales Lemoine <[email protected]> Hola colegas. ¿Alguien me podría ayudar con algún algoritmo para obtener todas las permutaciones posibles de un conjunto finito cualquiera? Por ejemplo, para el conjunto de 4 elementos ABCD las posibles permutaciones serían: 1. ABCD 2. ABDC 3. ACBD 4. ACDB 5. ADBC 6. ADCB 7. BACD 8. BADC 9. BCAD 10. BCDA 11. BDAC 12. BDCA 13. CABD 14. CADB 15. CBAD 16. CBDA 17. CDAB 18. CDBA 19. DABC 20. DACB 21. DBAC 22. DBCA 23. DCAB 24. DCBA Es decir, la cantidad de permutaciones sería igual al factorial de la cantidad de elementos del conjunto. En este caso 4! = 4 x 3 x 2 x 1 = 24. Agradecería cualquier sugerencia. Gracias. Saludos Ing. Tomás Corrales Lemoine -- Aeropuerto Internacional Frank País García de Holguín. -- Aeropuerto Internacional Frank País García de Holguín. -- Aeropuerto Internacional Frank País García de Holguín. -- Tanto si piensas que puedes, como si piensas que no puedes, estaras en lo cierto. (Henry Ford) Si no te gusta cómo las cosas están ahora, cámbialas! (Jim Rohn)
