elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Estamos en la red social de Mastodon


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Permutaciones en C++
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Permutaciones en C++  (Leído 24,920 veces)
#Aitor

Desconectado Desconectado

Mensajes: 173



Ver Perfil
Permutaciones en C++
« en: 13 Febrero 2015, 11:55 am »

La idea es sencilla pero llevo toda la mañana rompiéndome la cabeza. A partir de un string generar todas combinaciones posibles de n elementos.

Ejemplo:
Citar
A B C D

Siendo A string[0], y D string[3] resultados:

Citar
0 1 2 3
1 0 2 3
1 2 0 3
1 2 3 0
0 2 3 1
2 0 3 1
2 3 0 1
2 3 1 0
0 3 1 2
3 0 1 2
3 1 0 2
3 1 2 0
0 1 2 3
1 0 2 3
1 2 0 3
1 2 3 0
0 2 3 1
2 0 3 1
2 3 0 1
2 3 1 0
0 3 1 2
3 0 1 2
3 1 0 2
3 1 2 0

Principalmente intenté entender como funcionaba y como podría conseguir una pauta de sacar todas combinaciones, aquí ya hablare de todo el lío que se me pasó por la cabeza, al principio probé exclusivamente con 3 elementos, A, B, C la idea principal era sacar las 6 posibles combinaciones mediante una pauta a seguir, la idea era cambiar A dónde B, B dónde A generando una nueva palabra, después B dónde C, y C dónde B generando otra nueva palabra, y vuelta empezar hasta sacar las 6 combinaciones, el problema vino con elementos de cuatro, aquí empece a volverme loco al principió pensé que sería A dónde B, B dónde A. generando una nueva palabra, y después C dónde D y D dónde C generando otra nueva palabra y así sucesivamente, pero tras sacar 8 palabras nuevas, empezaban todas a repetirse, unas de las opciones que opté fue organizarlas por de menor a mayor

De la siguiente forma:

Citar
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1

1 0 2 3
1 0 3 2
1 2 0 3
1 2 3 0
1 3 0 2
1 3 2 0

2 0 1 3
2 0 3 1
2 1 0 3
2 1 3 0
2 3 0 1
2 3 1 0

3 0 1 2
3 0 2 1
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0

La idea ahora era que a la hora de programarlo, solo tuviese que tener en cuenta el código ASCII de los caracteres que componían la palabra e ir ordenándolos de menor a mayor, pero no vi como y me pareció una perdida de tiempo.

Finalmente me percaté (cielos, esto parece una novela xD) de qué la pauta que seguía independientemente de los elementos que cogiesen era A dónde B (Generando así nueva palabra) después B dónde C (Generando de nuevo otra nueva palabra) C dónde D (Generando, cómo no, una nueva palabra) y finalmente D dónde A y vuelta a empezar.

Si, efectivamente me encanta enrollarme pero quiero hacerme entender, llegados a este punto mi idea es la siguiente...

n! siendo n el tamaño del string, para después crear una tupla con el resultado de n! para recorrer un for n! veces y rellenar toda la tupla con las posibles combinaciones. El problema está en que no sé como narices puedo pasar String[0] por String[1] en la siguiente vuelta String[1] por String[2] y así sucesivamente hasta terminar con String[ejemplo.size-1] por String[ejemplo.size]

Código
  1. #include <iostream>
  2. #include <string>
  3.  
  4. using namespace std;
  5.  
  6. int main(){
  7. string palabra = "ABC";
  8.  
  9. int tam = palabra.size();
  10. int i, n_fact = 1;
  11.  
  12.    for(i=1; i<=tam; i++){
  13.  
  14.        n_fact = n_fact * i;
  15.    }
  16.  
  17.  
  18. string tabla[n_fact];
  19.    for (int it = 0; it < n_fact; it++){
  20.  
  21.    // Totalmente perdido en esta parte como indiqué...
  22.    cout << tabla[it] << endl;
  23.    }
  24.  
  25. }


« Última modificación: 13 Febrero 2015, 11:57 am por #Aitor » En línea

Mi algoritmo en PHP (estupideces y más).
Código
  1. while($Se_feliz){
  2.  Piensa_un_OBJETIVO(); // Sin excusas!
  3.  if($Tienes_un_objetivo){
  4.    Suspira(); // Sé paciente.
  5.    if($Consigues_el_objetivo){ echo "¡Felicidades #Aitor!";return;
  6.      //RETURN; ¿O volvemos a empezar?
  7.    }else{
  8.      Inténtalo_de_nuevo();
  9.    }
  10.  }
  11. }
eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: Permutaciones en C++
« Respuesta #1 en: 13 Febrero 2015, 12:08 pm »

Si tu idea es pegarte con ello por aprender, perfecto.

En caso contrario, lo que estás buscando ya existe:

Código
  1. #include <algorithm>
  2. #include <iostream>
  3.  
  4. int main( )
  5. {
  6.  std::string cadena = "ABCD";
  7.  
  8.  do
  9.  {
  10.    std::cout << cadena << std::endl;
  11.  } while ( std::next_permutation( cadena.begin( ), cadena.end( ) ) );
  12. }


En línea

#Aitor

Desconectado Desconectado

Mensajes: 173



Ver Perfil
Re: Permutaciones en C++
« Respuesta #2 en: 13 Febrero 2015, 12:38 pm »

Te agradezco el código, no tenía constancia de esa función (funciona a la perfección, por cierto) pero a la vez soy del colectivo imbécil que le encanta reinventar la rueda, como bien dices pienso que para aprender está genial.

Dicho esto agradecería seguir complicándome la vida con mi código aunque tiempo después de comprender como funciona acabase utilizando dicha función.

¡Un saludo y gracias!

EDITO: Por cierto, estuve probando unas cuantas palabras con ese código, y me sorprendió que con 'Amor' hubiese 24 posibles palabras (4 elementos, sin repetición 4!=24 combinaciones) Mientras que con Omar (4 elementos, sin repetición 4!=24 combinaciones también, y además siendo este una combinación de amor, solo mostrase 10 combinaciones) ¿A qué se debe?

Y con Pene solo dos... xD
« Última modificación: 13 Febrero 2015, 12:52 pm por #Aitor » En línea

Mi algoritmo en PHP (estupideces y más).
Código
  1. while($Se_feliz){
  2.  Piensa_un_OBJETIVO(); // Sin excusas!
  3.  if($Tienes_un_objetivo){
  4.    Suspira(); // Sé paciente.
  5.    if($Consigues_el_objetivo){ echo "¡Felicidades #Aitor!";return;
  6.      //RETURN; ¿O volvemos a empezar?
  7.    }else{
  8.      Inténtalo_de_nuevo();
  9.    }
  10.  }
  11. }
eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: Permutaciones en C++
« Respuesta #3 en: 13 Febrero 2015, 13:14 pm »

Te agradezco el código, no tenía constancia de esa función (funciona a la perfección, por cierto) pero a la vez soy del colectivo imbécil que le encanta reinventar la rueda, como bien dices pienso que para aprender está genial.

Una posible implementación de "next_permutation" copiada de la web cppreference:

Código
  1. template<class BidirIt>
  2. bool next_permutation(BidirIt first, BidirIt last)
  3. {
  4.    if (first == last) return false;
  5.    BidirIt i = last;
  6.    if (first == --i) return false;
  7.  
  8.    while (1) {
  9.        BidirIt i1, i2;
  10.  
  11.        i1 = i;
  12.        if (*--i < *i1) {
  13.            i2 = last;
  14.            while (!(*i < *--i2)) ;
  15.  
  16.            std::iter_swap(i, i2);
  17.            std::reverse(i1, last);
  18.            return true;
  19.        }
  20.        if (i == first) {
  21.            std::reverse(first, last);
  22.            return false;
  23.        }
  24.    }
  25. }

* Te he puesto el código directamente porque explicado queda un poco rebuscado
« Última modificación: 13 Febrero 2015, 13:16 pm por eferion » En línea

ginoob

Desconectado Desconectado

Mensajes: 1


Ver Perfil
Re: Permutaciones en C++
« Respuesta #4 en: 27 Mayo 2015, 08:18 am »

Este es mi algoritmo recursivo, creo que se explica solo :D
Código
  1. public class Main{
  2.  
  3. static int count=0;
  4.  
  5.    public static void combinaciones(String primero,String cadena) {
  6.  
  7.     if(cadena.length()==2)
  8.     {
  9.     count=count+2;
  10.     System.out.println(primero+cadena.charAt(1)+""+cadena.charAt(0));
  11.     System.out.println(primero+cadena.charAt(0)+""+cadena.charAt(1));
  12.     }
  13.     else{
  14.     for (int i=0;i<cadena.length();i++) {    
  15.       combinaciones(primero+cadena.charAt(i),quitarLetra(cadena,i));
  16.     }
  17.     }      
  18.    }
  19.    public static String quitarLetra(String cadena,int i)
  20.    {
  21.     if(i==0)
  22.     {
  23.     return cadena.substring(i+1,cadena.length());
  24.     }
  25.     else
  26.     {
  27.     if(i==cadena.length())
  28.     {
  29.     return cadena.substring(0,cadena.length()-1);
  30.     }
  31.     else
  32.     {
  33.     return cadena.substring(0,i)+cadena.substring(i+1,cadena.length());
  34.     }
  35.     }    
  36.    }
  37.    public static void main(String args[]) {
  38.     String cadena="abcda";    
  39.     System.out.println("combinaciones de :"+cadena);    
  40.     combinaciones("",cadena);
  41.     System.out.println("total:"+count);            
  42.    }
  43. }
  44.  
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Ayuda] permutaciones .net
.NET (C#, VB.NET, ASP)
oscarj24 3 4,269 Último mensaje 29 Abril 2011, 22:54 pm
por oscarj24
Problema con formula para generar permutaciones
Programación C/C++
Blaster 9 8,037 Último mensaje 2 Enero 2014, 19:01 pm
por do-while
Programa de combinaciones y permutaciones en python
Ejercicios
jorgeeo_O 0 5,698 Último mensaje 30 Octubre 2014, 23:19 pm
por jorgeeo_O
Diccionarios de permutaciones?
Hacking Wireless
gado2612 1 3,202 Último mensaje 9 Abril 2016, 14:19 pm
por tincopasan
Programa en C de permutaciones
Programación C/C++
JuanJose97ortiz 2 4,734 Último mensaje 29 Junio 2019, 15:55 pm
por @XSStringManolo
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines