Una forma sencilla y rápida de aprender JAVA, observando y deduciendo cómo se comporta el lenguaje a través de ejemplos prácticos.

lunes, 18 de junio de 2012

Permutaciones: Sin repetición / Importa orden. (forma recursiva)

Codigo:

//* Permutaciones (Forma recursiva)
//- Importa posición
//- Sin repetición
//- Requisito: R >= N
package permutacion2;

public class Permutacion2 {

    public static void main(String[] args) {
        String[] elementos = "a,b,c,d,e".split(",");
        int n = 4;                  //Tipos para escoger
        int r = elementos.length;   //Elementos elegidos
        Perm2(elementos, "", n, r);
    }

    private static void Perm2(String[] elem, String act, int n, int r) {
        if (n == 0) {
            System.out.println(act);
        } else {
            for (int i = 0; i < r; i++) {
                if (!act.contains(elem[i])) { // Controla que no haya repeticiones
                    Perm2(elem, act + elem[i] + ", ", n - 1, r);
                }
            }
        }
    }
}

Resultado:

run:
a, b, c, d,
a, b, c, e,
a, b, d, c,
...
...
...
e, d, b, c,
e, d, c, a,
e, d, c, b,
BUILD SUCCESSFUL (total time: 0 seconds)

27 comentarios:

  1. Hola muchisimas gracias, tu código me ha servido de maravilla sorprendentemente ya lo adopte a lo que necesitaba y digo sorprendentemente porque no termino de entender toda la lógica del metodo Perm2 xD me ayudaría mucho si me explicaras ya que no me sentiré conforme si no entiendo del todo, de antemano muchisimas gracias.

    ResponderEliminar
  2. Una consulta, y si lo quisiera mostrar en orden aleatorio, en dónde alteraría el código?

    ResponderEliminar
    Respuestas
    1. Quizás te sirva el siguiente codigo.
      http://censorcosmico.blogspot.com.es/2013/01/generar-numeros-aleatorios-sin.html
      Se me ocurre que podrias usar los números aleatorios sin repeticion generados como un indice de una lista de objetos.

      Eliminar
  3. Me gustaría saber de donde obtuviste el algoritmo o el pseudocodigo o si es una idea tuya, pues me gustaría usarlo para un trabajo y me gustaría referenciar.

    ResponderEliminar
    Respuestas
    1. No encontré ningún codigo que cumpliera el requisito de "sin repeticiones", asi que lo cree yo mismo.

      Eliminar
  4. en que cambia si deseo que el r sea distinto es decir solo selccionar dos elemntos

    ResponderEliminar
    Respuestas
    1. Prueba modificar esas dos variables. Y ten en cuenta que: r >= n.
      int n = 2;
      int r = 2;

      Eliminar
  5. si yo quiesiera permutar todas las letras del ABC y r fuera aumentado hasta r=27...como seria

    ResponderEliminar
    Respuestas
    1. String[] elementos = "a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,w,x,y,z".split(",");
      int r = elementos.length;

      Eliminar
  6. una consulta como hago para que en pantalla me pida la cantidad de veces que deceo permutar

    ResponderEliminar
    Respuestas
    1. supongo que te refieres a pedir los valores de n y r, tendrias que usar el siguiente bloque de codigo sustituyendo las dos lineas donde le damos valor a n y r
      Scanner entrada=new Scanner(System.in);//creamos objeto entrada
      int n,r;// declaramos las variables n y r
      System.out.println("Ingrese valor de n");//mandamos un mensaje a consola para que nos pida el valor de n
      entrada=n.nextInt();//guardamos el valor introducido en la variable n
      System.out.println("Ingrese valor de r");//mandamos un mensaje a consola para que nos pida el valor de r
      entrada=r.nextInt();//guardamos el valor introducido en la variable r
      espero haber ayudado
      suerte

      Eliminar
    2. una disculpa tuve un error de escritura el codigo queda de la siguiente manera
      Scanner entrada=new Scanner(System.in);//creamos objeto entrada
      int n,r;// declaramos las variables n y r
      System.out.println("Ingrese valor de n");//mandamos un mensaje a consola para que nos pida el valor de n
      n=entrada.nextInt();//guardamos el valor introducido en la variable n
      System.out.println("Ingrese valor de r");//mandamos un mensaje a consola para que nos pida el valor de r
      r=entrada.nextInt();//guardamos el valor introducido en la variable r
      si te marca errores solo borra los comentarios

      Eliminar
  7. Muchas gracias, el codigo me ha servido lo he implementado en un jframe que me pide los valores de n y r y va de maravilla, pero si yo quiero realizar las combinaciones con repeticion y sin repeticion ¿como le haria?

    ResponderEliminar
  8. Una consulta si deseo hacer las combinaciones con repeticion y sin repeticion ¿como le haria?

    ResponderEliminar
  9. Lo convertí a iterativo en C# a ver que te parece:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace ConsoleApplication2
    {
    class Program
    {
    static void Main(string[] args)
    {
    string[] pal = { "A", "B", "C" };
    Permutar(pal, pal.Length);
    Console.ReadLine();
    }

    public static void Permutar(string[] elem, int n)
    {
    Queue cola = new Queue();

    cola.Enqueue(new Dato("", n));

    while (cola.Count > 0)
    {
    Dato d = cola.Dequeue();
    if (d.n == 0)
    {
    Console.WriteLine(d.act);
    }
    else
    {
    for (int i = 0; i < elem.Length; i++)
    {
    if (!d.act.Contains(elem[i]))
    {
    cola.Enqueue(new Dato(d.act + elem[i], d.n - 1));
    }
    }
    }
    }
    }
    }

    public class Dato
    {
    public string act;
    public int n;

    public Dato(string act, int n)
    {
    this.act = act;
    this.n = n;
    }
    }
    }

    ResponderEliminar
  10. creo que nunca me dara la cabeza para hacer algo asi xd
    muy buena logica (y)

    ResponderEliminar
  11. Que tal disculpa si quisiera Usar tu código pero en android studio, me pidieron una app muy básica para permutaciones pero nuestros exámenes serán referente a ello crees que te pueda contactar incluso unos chavos andan ofreciendo $$ mi correo es danielb.mendoza@hotmail.com

    ResponderEliminar
  12. Como haria para que me muestre la permutacion por ejemplo de aab

    ResponderEliminar
  13. Perm2(elem, act + elem[i] + ", ", n - 1, r); q haces akiexactamente ?

    ResponderEliminar
  14. Disculpa, si quisiera incluir duplicados con el codigo en C#, ¿como lo haria?

    ResponderEliminar
  15. como seria en c++ el programa

    ResponderEliminar
  16. Exelecte codigo y facil para trabajar una matriz binaria!!

    ResponderEliminar
  17. Disculpa, como imprimes el resultado con JOptionPane?

    ResponderEliminar
  18. $elementos = "abc";
    $n=3; // Tipos para escojer
    $r=strlen($elementos); // Elementos elegidos
    perm2($elementos, "", $n, $r);


    function perm2($elem, $act, $n, $r) {
    if($n == 0) {
    echo $act . "\n";
    } else {
    for($i=0; $i<$r; $i++) {
    if(preg_match("/".$elem[$i]."/i", $act) == false) {
    perm2($elem, $act . $elem[$i], $n-1, $r);
    }
    }
    }
    }

    ResponderEliminar
  19. gran solución,peor como haria para discriminar algunas combinaciones que no cumplan un patron determinado

    ResponderEliminar

Con la tecnología de Blogger.