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.

Archivo del blog

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)

35 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
    Respuestas
    1. Coje un lapiz y papel y empieza hacerlo paso por paso tu mism@ y lo entenderas ;) , te recomiendo solo con un arreglo {a , b , c} para que no se te haga largo

      Eliminar
  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
  20. Muchas gracias por la ayuda. Funciona correctamente

    ResponderEliminar
  21. y con repeticion ejemplo "abc" se tome como un valor diferente a "acb"

    ResponderEliminar
  22. Y si no quiero q "a" y "b" que no estén juntos, como sería?

    ResponderEliminar
  23. me puede coloaborar con un ejercicio en java

    ResponderEliminar
  24. El problema de ese ejemplo es que, la función deja de funcionar cuando hay una cadena tipo "a,b,b,c" es decir, con valores repetidos.

    Dejo la función hecha en Javascript que funciona tambien con valores repetidos por si alguno le interesa:

    function PrimeChecker(num) {

    // code goes here
    let arrayNum = num.toString().split('');
    let arrayJoin = permutacion(arrayNum, "", arrayNum.length, arrayNum.length, []);
    let unique = [...new Set(arrayJoin)];
    for (let i = 0; i < unique; i++) {
    const element = parseInt(unique[i]);
    if(isPrime(element)){
    return 1;
    }
    }
    return 0;

    }

    function permutacion(array, actual, n, r, arrayJoin){

    if (n == 0) {
    arrayJoin.push(actual);
    } else {
    for (let i = 0; i < r; i++) {
    let arraycopied = [...array];
    arraycopied.splice(i,1);
    permutacion(arraycopied, actual + array[i] + "", n - 1, r-1, arrayJoin);
    }
    }
    return arrayJoin;
    }

    function isPrime(num){
    for (let i = 2; i < num; i++) {
    if(num % i === 0){
    return false;
    }
    }
    return num > 1;
    }

    ResponderEliminar
  25. Hola buenas noches
    ¿Cómo puedo separar las palabras existentes que se forma en la permutación?
    es decir si tengo
    a,s,p,o
    como podre separar las palabras
    paso,sapo,sopa
    ¿Cómo lo hago de antemano gracias.

    ResponderEliminar

Con la tecnología de Blogger.