Generación de un número aleatorio basado en una función de probabilidad.

El siguiente algoritmo genera números aleatorios no uniformes. La premisa es dar un porcentaje de probabilidad para que aparezca cierto número en un rango dado.

Ejemplo:
Generar un número aleatorio del 1 al 350 del cual el número 56 tenga un 34.9% de probabilidad de que salga elegido. Las entradas serían las siguientes:

rango = 350
numero = 56
ratio = 0.349


Código Java 1 (AleatorioCondicionado1.java)

package aleatoriocondicionado1;

public class AleatorioCondicionado1 {

   public static void main(String[] args) {

      RandA randa = new RandA();     
      int max = 350;
      int num = 56;
      float ratio = 0.349F;
      int valor = randa.getRandA(max, num, ratio);
     
      System.out.println("Rango: [1:" + max + "]");
      System.out.println("Numero: " + num);
      System.out.println("Ratio%: " + ratio);     
      System.out.println("Valor obtenido: " + valor);

   }

}


Código Java 2 (RandA.java):

package aleatoriocondicionado1;

import java.util.Random;

public class RandA {

   Random r = new Random();

   int getRandA(int max, int num, float ratio) {
      float x;
      int rand = r.nextInt(max) + 1;
      x = max * ratio;
      if (rand <= x) {
         return num;
      } else {
         do {
            rand = r.nextInt(max) + 1;
         } while (rand == num);
         return rand;
      }
   }

}
 

Resultado:

run:
Rango: [1:350]
Numero: 56
Ratio%: 0.349
Valor obtenido: 56
BUILD SUCCESSFUL (total time: 1 second)

Nota: Si ejecutamos muchas veces el mismo código se comprueba de que el número 56 tiende a salir en una proporción mayor al resto de números, concretamente saldría en un 34.9 % de los casos.

Cálculo del grado de similitud entre dos palabras. Distancia de Levenshtein.

Una forma para obtener el grado de similitud entre dos palabras distintas es calculando la distancia de Levenshtein, que consiste en calcular el número mínimo de operaciones necesarias para transformar una cadena de caracteres en otra. Obtenida esta distancia podemos calcular fácilmente el grado de similitud porcentual (afinidad) entre las dos palabras:

Afinidad = 1 - (D / L)

D: Distancia de Levenshtein.
L: Longitud de la palabra más larga. 


Código Java 1: (Levenshtein1.java)

// Calculo del grado de similitud entre dos palabras distintas.
package levenshtein1;

public class Levenshtein1 {

   public static void main(String[] args) {

      String str1 = "identificar";
      String str2 = "identify";

      LevenshteinDistance ld = new LevenshteinDistance();
      ld.setWords(str1, str2);

      // Mostrar resultados
      System.out.println("Palabra1: " + str1);
      System.out.println("Palabra2: " + str2);
      System.out.println("\nDistancia de Levenshtein:\n" + ld.getDistancia());
      System.out.println("Afinidad:\n" + ld.getAfinidad() * 100 + " %");

   }

}


Código Java 2: (LevenshteinDistance.java)

package levenshtein1;

public class LevenshteinDistance {

   private String str1;
   private String str2;
   private int distancia;
   private int[][] matriz;

   public void setWords(String str1, String str2) {
      this.str1 = str1.toLowerCase();
      this.str2 = str2.toLowerCase();
      calculoLevenshtein();
   }

   public int getDistancia() {
      return distancia;
   }

   public float getAfinidad() {
      float longitud = str1.length() > str2.length() ? str1.length() : str2.length();
      return 1 - (distancia / longitud);
   }

   private void calculoLevenshtein() {
      matriz = new int[str1.length() + 1][str2.length() + 1];
      for (int i = 0; i <= str1.length(); i++) {
         matriz[i][0] = i;
      }
      for (int j = 0; j <= str2.length(); j++) {
         matriz[0][j] = j;
      }
      for (int i = 1; i < matriz.length; i++) {
         for (int j = 1; j < matriz[i].length; j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
               matriz[i][j] = matriz[i - 1][j - 1];
            } else {
               int min = Integer.MAX_VALUE;
               if ((matriz[i - 1][j]) + 1 < min) {
                  min = (matriz[i - 1][j]) + 1;
               }
               if ((matriz[i][j - 1]) + 1 < min) {
                  min = (matriz[i][j - 1]) + 1;
               }
               if ((matriz[i - 1][j - 1]) + 1 < min) {
                  min = (matriz[i - 1][j - 1]) + 1;
               }
               matriz[i][j] = min;
            }
         }
      }
      distancia = matriz[str1.length()][str2.length()];
   }

}


Resultado:

run:
Palabra1: identificar
Palabra2: identify

Distancia de Levenshtein: 4
Afinidad: 63.636364 %
BUILD SUCCESSFUL (total time: 0 seconds)

Tests de eficiencia sobre algoritmos de creación de números aleatorios sin repetición.

Código Java (AleatorioSinRepeticion1.java):

/**
 * Tests de eficiencia sobre diferentes algoritmos de creación de números
 * aleatorios sin repetición.
 */

package aleatoriosinrepeticion1;

import java.util.Random;
import java.util.Stack;

public class AleatorioSinRepeticion1 {

    public static void main(String[] args) {

        long precision = 1000000;
        int nNodos = 13;

        test1(nNodos, precision);// Eficiencia base
        test2(nNodos, precision);// Eficiencia +620%
        test3(nNodos, precision);// Eficiencia +1156%

    }

    private static void test1(int nNodos, long precision) {

        int perm[] = new int[nNodos];
        int pos;

        long tiempo1 = System.nanoTime();
        for (int k = 0; k < precision; k++) {
            Stack<Integer> pRuta = new Stack<Integer>();
            for (int i = 0; i < nNodos; i++) {
                pos = (int) Math.floor(Math.random() * nNodos);
                while (pRuta.contains(pos)) {
                    pos = (int) Math.floor(Math.random() * nNodos);
                }
                pRuta.push(pos);
                perm[i] = pos;
            }
        }
        long tiempo2 = System.nanoTime();

        System.out.println("Tiempo1: " + (tiempo2 - tiempo1) / 1e6 + " ms");
    }

    private static void test2(int nNodos, long precision) {

        Stack<Integer> pRef = new Stack<Integer>();
        int perm[] = new int[nNodos];
        Random rnd = new Random();
        int pos;

        long tiempo1 = System.nanoTime();
        for (int k = 0; k < precision; k++) {
            for (int i = 0; i < nNodos; i++) {
                pRef.add(i);
            }
            for (int i = 0; i < nNodos; i++) {
                pos = rnd.nextInt(pRef.size());
                perm[i] = pRef.remove(pos);
            }
        }
        long tiempo2 = System.nanoTime();

        System.out.println("Tiempo2: " + (tiempo2 - tiempo1) / 1e6 + " ms");
    }

    private static void test3(int nNodos, long precision) {

        int[] aux_perm = new int[nNodos];
        Random rnd = new Random();
        int[] perm = new int[nNodos];
        int aux_nNodos = nNodos;
        int pos;

        long tiempo1 = System.nanoTime();
        for (int index = 0; index < precision; index++) {
            aux_nNodos = nNodos;
            for (int i = 0; i < nNodos; i++) {
                aux_perm[i] = i + 1;
            }
            for (int i = 0; i < nNodos; i++) {
                pos = rnd.nextInt(aux_nNodos);
                perm[i] = aux_perm[pos] - 1;
                aux_perm[pos] = aux_perm[aux_nNodos - 1];
                aux_nNodos--;
            }
        }
        long tiempo2 = System.nanoTime();

        System.out.println("Tiempo3: " + (tiempo2 - tiempo1) / 1e6 + " ms");
    }

}

Resultado:

run:

Tiempo1: 9470.44684 ms

Tiempo2: 1515.179325 ms

Tiempo3: 823.204608 ms

BUILD SUCCESSFUL (total time: 11 seconds)