Permutaciones en C++

[#Aitor]

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:

A B C D

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

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:

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 (c++) [Seleccionar] Expandir

#include <iostream>
#include <string>

using namespace std;

int main(){
string palabra = "ABC";

int tam = palabra.size();
int i, n_fact = 1;

   for(i=1; i<=tam; i++){

       n_fact = n_fact * i;
   }


string tabla[n_fact];
   for (int it = 0; it < n_fact; it++){

   // Totalmente perdido en esta parte como indiqué...
   cout << tabla[it] << endl;
   }

}

[eferion]

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

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

Código (cpp) [Seleccionar] Expandir

#include <algorithm>
#include <iostream>

int main( )
{
  std::string cadena = "ABCD";

  do
  {
    std::cout << cadena << std::endl;
  } while ( std::next_permutation( cadena.begin( ), cadena.end( ) ) );
}

[#Aitor]

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

[eferion]

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 (cpp) [Seleccionar] Expandir

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
   if (first == last) return false;
   BidirIt i = last;
   if (first == --i) return false;

   while (1) {
       BidirIt i1, i2;

       i1 = i;
       if (*--i < *i1) {
           i2 = last;
           while (!(*i < *--i2)) ;

           std::iter_swap(i, i2);
           std::reverse(i1, last);
           return true;
       }
       if (i == first) {
           std::reverse(first, last);
           return false;
       }
   }
}

* Te he puesto el código directamente porque explicado queda un poco rebuscado

[ginoob]

Este es mi algoritmo recursivo, creo que se explica solo

Código (java) [Seleccionar] Expandir


public class Main{

static int count=0;

    public static void combinaciones(String primero,String cadena) {

    if(cadena.length()==2)
    {
    count=count+2;
    System.out.println(primero+cadena.charAt(1)+""+cadena.charAt(0));
    System.out.println(primero+cadena.charAt(0)+""+cadena.charAt(1));
    }
    else{
    for (int i=0;i<cadena.length();i++) {   
        combinaciones(primero+cadena.charAt(i),quitarLetra(cadena,i));
    }
    }     
    }
    public static String quitarLetra(String cadena,int i)
    {
    if(i==0)
    {
    return cadena.substring(i+1,cadena.length());
    }
    else
    {
    if(i==cadena.length())
    {
    return cadena.substring(0,cadena.length()-1);
    }
    else
    {
    return cadena.substring(0,i)+cadena.substring(i+1,cadena.length());
    }
    }   
    }
    public static void main(String args[]) {
    String cadena="abcda";   
    System.out.println("combinaciones de :"+cadena);   
    combinaciones("",cadena);
    System.out.println("total:"+count);           
    }
}