Permutaciones, combinaciones, variaciones y particiones

Librería en Java para generar permutaciones, combinaciones, variaciones y particiones, con un programa para testearlas.



Permutador.java

package combinatoria;

 public class Permutador {
    private int fact;
    private int cuenta;
    private int[] vector;
    
    public Permutador(int[] vec) {
        vector = vec;
        cuenta = 0;
    }
    
    // genera una nueva permutación del vector
    // retorna true si aún quedan permutaciones
    // o false si las ha generado todas 
    public boolean permutar() {
        return permutar(0, vector.length);
    }
    
    boolean permutar(int inicio, int tam) {
        if(tam > 1) {
            if(!permutar(inicio + 1, tam - 1)) {
                rotar(inicio);
            }
            fact *= tam;
        } else {
            cuenta++;
            fact = 1;
        }
        
        return cuenta % fact != 0;
    }
    
    void rotar(int inicio) {
        int i, primero;

         primero = vector[inicio];

         for(i = inicio + 1; i < vector.length; i++) {
            vector[i-1] = vector[i];
        }

         vector[i-1] = primero;
    }

 }

 Combinador.java

package combinatoria;

import java.util.ArrayList;

public class Combinador {
    
    public static ArrayList<int[]> combinar(int[] vec, int tam) {
        ArrayList<int[]> lista = new ArrayList<>();

        if(tam > 0 && tam <= vec.length) {
            Permutador p = new Permutador(vec);
            int[] sub = new int[tam];
            
            do {
                for(int i = tam-1; i < vec.length; i++) {
                    int j = i;
                    int k = tam;
                    while(k > 0) {
                        sub[--k] = vec[j--];
                    }
                    ordenar(sub);
                    for(j = 0; j < lista.size() && 
                        !igual(sub, lista.get(j)); j++);
                    
                    if(j == lista.size()) {
                        lista.add(sub.clone());
                    }
                }
                
            } while(p.permutar());
        }
        
        return lista;
    }
    
    static boolean igual(int[] p, int[] q) {
        int i;

        for(i = 0; i < p.length && p[i] == q[i]; i++);
        
        return i == p.length;
    }
    
    static void ordenar(int[] v) {
        boolean hayCambio;
        int t = v.length;
        
        do {
            hayCambio = false;
            for(int i = 1; i < t; i++) {
                if(v[i-1] > v[i]) {
                    int x = v[i];
                    v[i] = v[i-1];
                    v[i-1] = x;
                    hayCambio = true;
                }
            }
            t--;
        } while(hayCambio);
    }

}

Variador.java

package combinatoria;

import java.util.ArrayList;

public class Variador {

    public static ArrayList<int[]> variar(int[] vec, int tam) {
        ArrayList<int[]> lista = new ArrayList<>();

        if(tam > 0 && tam <= vec.length) {
            Permutador p = new Permutador(vec);
            int[] sub = new int[tam];
            
            do {
                for(int i = tam-1; i < vec.length; i++) {
                    int j = i;
                    int k = tam;
                    while(k > 0) {
                        sub[--k] = vec[j--];
                    }
                    
                    for(j = 0; j < lista.size() && 
                        !igual(sub, lista.get(j)); j++);
                    
                    if(j == lista.size()) {
                        lista.add(sub.clone());
                    }
                }
                
            } while(p.permutar());
        }
        
        return lista;
        
    }
    
    // p.length == q.length
    static boolean igual(int[] p, int[] q) {
        int i;

        for(i = 0; i < p.length && p[i] == q[i]; i++);
        
        return i == p.length;
    }
}

Particion.java

package combinatoria;

import java.util.ArrayList;

public class Particion implements Cloneable, Comparable<Particion> {
    public final ArrayList<Integer> partes;
    public int numero;
    
    private Particion() {
        partes = new ArrayList<>();
    }
    
    Particion(int num) {
        this();
        numero = num;
        partes.add(num);
    }
    
    private void setNumero(int num) {
        numero = num;
    }
    
    @Override
    protected Particion clone() {
        Particion nueva = new Particion();
        nueva.setNumero(numero);
        
        for(int i : partes) {
            nueva.partes.add(i);
        }

        return nueva;
    }
    
    void extender() {
        partes.add(0, partes.remove(0)-1);
        partes.add(1);
    }
    
    void agrupar(int i) {
        int val = partes.get(i) + partes.get(i+1);
        partes.remove(i+1);
        partes.remove(i);
        partes.add(i, val);
    }
    
    int get(int i) {
        return i < partes.size()? partes.get(i) : 0;
    }
    
    public int size() {
        return partes.size();
    }
    
    public int[] toArray() {
        int tam = 0;
        
        for(int p : partes) {
            tam += p;
        }
        
        return toArray(tam);
    }
    
    public int[] toArray(int tam) {
        int[] vec = new int[tam];
        
        int i = 0;
        while(i < tam && i < partes.size()) {
            vec[i] = partes.get(i);
            i++;
        }
        
        while(i < tam) {
            vec[i++] = 0;
        }
        
        return vec;
    }
    
    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        
        for(int i : partes) {
            sb.append(" " + i);
        }
        
        return sb.toString();
    }

    @Override
    public int compareTo(Particion otra) {
        int lim = size() < otra.size() ? size() : otra.size();
        int dif = get(0) - otra.get(0);
        int i = 0;
        
        while(dif == 0 && ++i < lim) {
            dif = get(i) - otra.get(i);
        }
        
        return dif;
    }
}

Partidor.java

package combinatoria;

import java.util.ArrayList;

public class Partidor {
    public final ArrayList<Particion> particiones;
    public final int numero;

    public Partidor(int num) {
        this.numero = num;
        particiones = new ArrayList<Particion>();
        particiones.add(new Particion(num));
        extender(0);
    }
    
    void extender(int i) {
        Particion par = particiones.get(i);
        
        if(par.get(0) > 1) {
            Particion nueva = par.clone();
            nueva.extender();
            particiones.add(nueva);
            extender(i+1);
        } else {
            agrupar(0, 1);
        }
    }
    
    void agrupar(int i, int pos) {
        Particion par = particiones.get(i);

        if(pos < par.size() - 1) {
            int anterior = par.get(pos-1);
            int nuevo = par.get(pos) + par.get(pos+1);
            if(nuevo <= anterior) {
                Particion nueva = par.clone();
                nueva.agrupar(pos);
                particiones.add(nueva);
            }
        }
        
        if(++i < particiones.size()) {
            agrupar(i, pos);
        } else if(++pos < numero-2) {
            agrupar(0, pos);
        }
    }
    
    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        
        int j = 0;
        for(Particion p : particiones) {
            sb.append(String.format("\n[%2d] ", ++j) + p);
        }
    
        return sb.toString() + "\n";
    }
    
    public void ordenar() {
        boolean hayCambio;
        int tam = particiones.size();
            
        do {
            hayCambio = false;
            Particion p = particiones.get(0);
            for(int i = 1; i  < tam; i++) {
                Particion q = particiones.get(i);
                if(p.compareTo(q) < 0) {
                    particiones.set(i-1, q);
                    particiones.set(i, p);
                    hayCambio = true;
                } else {
                    p = q;
                }
            }
            tam--;
        } while(hayCambio);
    }
    
    public ArrayList<Particion> get() {
        return particiones;
    }
    
    public static ArrayList<int[]> partir(int num) {
        ArrayList<Particion> particiones = 
            new Partidor(num).particiones;
        ArrayList<int[]> lista = new ArrayList<>();
        for(Particion p : particiones) {
            lista.add(p.toArray());
        }
        return lista;
    }

}

Comentarios

Publicar un comentario

Entradas populares de este blog

Fractales

Imagen
Fractales configurables de Mandelbrot y Julia en Java (Eclipse neon.3). Deacargar código fuente Descargar .jar ejecutable Referencia al conjunto de Mandelbrot en Wikipedia Referencia al conjunto de Julia en Wikipedia El código fuente es demasiado extenso para publicarlo acá, pero se puede descargar libremente. A continuación algunas capturas de pantalla con diferentes configuraciones. Pantalla inicial Algunos fractales con el conjunto de Mandelbrot  Algunos fractales con el conjunto de Julia Paleta de colores para 300 iteraciones.
Leer más

Vida

Imagen
Vida es un programa en Java (Eclipse neon.3) que permite jugar al juego de la vida de John H. Conway. Descargar código fuente Descargar Vida.jar ejecutable Referencia del Juego de la Vida en Wikipedia Esquema.java package vida; /**  * Representa un patrón con su posición en la matriz  * @author Horacio Bono  */ public class Esquema {     public final int fil;     public final int col;     public final Patron patron;          public Esquema(int fil, int col, Patron patron) {         this.fil = fil;         this.col = col;         this.patron = patron;     }          public boolean mismaPosicion(Esquema otro) {         return this.fil == otro.fil && this.col == otro.col;     }          public boolean mismoPatron(Esquema otro) { ...
Leer más