[SOLUCIONADO] Combinaciones de números aleatorios que no se repitan

[NSD]

Buenas tardes gente, tengo un problema que en un principio lo subestime como algo trivial pero al cual no le encuentro una solución aceptable.

Un cliente quiere hacer una especie de bingo electrónico, para lo cual, cada jugador tiene vinculados 15 números del 0 al 99 que debe generar el sistema de forma automática.

Las 3 reglas básicas son:

- No puede haber mas de 2 números repetidos en el mismo cartón.
- No puede haber cartones repetidos.
- El orden no importa.

Los puntos 1 y 3 no son difíciles, pero el punto 2 no se como resolverlo.
Pensé en tener 2 tablas en la base de datos:

-- Clientes --
Codigo Integer Autoincrement PK
Nombre CHAR
...

-- Cartones --
Codigo Integer Autoincrement PK
Cliente Integer FK(Clientes.Codigo)
Numero_1 Integer
Numero_2 Integer
Numero_3 Integer
Numero_4 Integer
Numero_5 Integer
Numero_6 Integer
Numero_7 Integer
Numero_8 Integer
Numero_9 Integer
Numero_10 Integer
Numero_11 Integer
Numero_12 Integer
Numero_13 Integer
Numero_14 Integer
Numero_15 Integer

Solución 1:
El algoritmo en php generaría 15 números al azar, los ordenaría y los guardaría en la tabla cartones.
Para saber si no esta esa combinación, esta acción estaría dentro de un while.
El problema de esto es claro: Cuando tenga mas de la mitad de las combinaciones insertadas, agregar un nuevo cartón al azar tardaría un montón y consumiría un montón de recursos y podría tardar mucho tiempo.

Solución 2:
Pre-Poblar la tabla cartones con todas las combinaciones posibles (Un montooooon) y luego seleccionar un cartón al azar de esa tabla que no este asignado para cada cliente nuevo.
Problema: La tabla Cartones es enorme, aun con pocos clientes.

¿Se les ocurre alguna otra solución posible?

[informacionsys]

tengo una duda; el mismo numero si puede estar en n cartones ? es valido que tengas un carton con los numeros 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 y otro casi igual pero en vez del 14 el 16.

[NSD]

Si es valido.

No puede haber cartones iguales y no se puede repetir el numero dentro del cartón, pero si puede aparecer el mismo numero en muchos cartones.

[pateketrueke]

El punto (2) yo lo veo extremadamente fácil, que claro, si lo quieres hacer con consultas a la base de datos entonces ya no es tan simple.

Es decir, ¿si antes de cargar todas las combinaciones en la base de datos revisas si hay duplicados no sería mejor?

Vamos, que si agregas de a uno por uno, y luego para validar repeticiones vas a la base de datos ahí ya tienes un problema de diseño: y hasta de sentido común.

Usando estructuras simples:

Código PHP:

$tabla = [
  [1, 2, 3, 4],
  [9, 6, 5, 8],
  /* ... */
];
 

Ahora, ya teniendo una lista de listas, procedes a ordenar de manera natural cada sublista, de ahí puedes convertirlo a una cadena de texto.

Código PHP:

$lista = [
  '1.2.3.4',
  '5.6.8.9',
  /* ... */
];
 

La solución se explica sola: como ya has reducido la lista de listas a una lista más simple entonces ahí aplicas array_unique() para descartar duplicados, etc.

En fin, hay muchas forma de hacer esto y la mejor forma es hacerlo en memoria.

No intentes resolver un problema estructural con base de datos.

[informacionsys]

hola..

esta es una idea para que te guies...

Código PHP:

function getCartones()
{
    $fnNumbers = function()
    {   
        for($i2 = 1 ; $i2  <= 99 ; $i2++)
        {
            $n[] = $i2;
        }
        return $n;
    };
 
    $numbers     = $fnNumbers();//arreglo con los numeros aleatorios posibles   
    $totCartones = floor(count($numbers)/15);   //cantidad de cartones a crear
 
    function fnCarton($list,$numbers=array())
    {   
        if(!empty($numbers))
        {
            for($row = 1 ; $row <= 15 ; $row++)
            {
                $nro  = array_rand($numbers,1);
 
                if(in_array($nro,$numbers) && !empty($nro))
                {
                    $list[] = $nro;
                    $key    = array_search($nro,$numbers);
                    unset($numbers[$key]);
                }
 
                if(count($list) < 15 )
                {
                   return fnCarton($list,$numbers);
                }
                else
                {
                    return $list;
                }
            };//fin for             
        }
    };  
 
    for($ic = 0 ; $ic < $totCartones ; $ic++)
    {
        $list           = array();//arreglo con los 15 numeros posibles por carton
        $dataCartones[] = fnCarton($list,$numbers);
    }
    return $dataCartones;   
};
$car =getCartones();
var_dump($car);
 

[NSD]

Gracias por sus respuestas, pero creo que no me exprese bien, tratare de explicarme un poco mejor.

El usuario da de alta cada tanto nuevos clientes, en el momento del alta, el sistema le asigna a ese cliente un cartón generado aleatoriamente que no debe estar asignado a ningún otro cliente previo.

En la base de datos, se guardan los clientes y los cartones que tiene asociado cada uno.

El problema es como generar un cartón QUE NO ESTE ASIGNADO A NINGÚN OTRO CLIENTE de los que ya están registrados.

Levantar a memoria todos los cartones registrados para luego armar uno nuevo, puede voltearme el server ya que van a ser muchísimos.

Se me ocurrió otra posibilidad que es muy viable y genérica, pero que no logro hacerla funcionar, la idea es esta:

Dado un conjunto de elementos cualquiera, se pueden obtener una lista de todas sus combinaciones de elementos de forma ordenada sin problemas, ahora, si pudiera obtener directamente una combinación de esa lista, sin calcular las demás, podría guardar el numero de carton del cliente como un entero comun, y luego al vuelo obtener la combinacion de numeros correspondiente.

El problema que tengo es que no logro que la funcion ande, ¿Me podrían dar una mano?

Código PHP:

<?php
    function factorial($numero)
    {
        $fact = 1;
        while($numero >= 1 && ($fact *= $numero--));
        return $fact;
    }
    
    function combinatoria($m, $n)
    {
        return (factorial($m) / (factorial($n) * factorial($m - $n)));
    }
    
    // Esta funcion obtiene la combinacion de una posicion.
    // Items es un array con los elementos
    // $n el numero de elementos por carton
    // $pos es la posicion que me interesa
    function cartones($items, $n, $pos)
    {
        // Aca se guardan los items del carton
        $combinacion = [];         
        // Cuantos items hay
        $m = count($items);
                   
        // Auxiliares
        $base = 0;
        $idx = -1;
        // Mientras me falte algun elemento en la combinacion
        while($n)
        {
            //echo "<hr>";
            // Numero de combinaciones posibles
            $posibles = combinatoria($m, $n);
            // Para cada variacion de 1 elemento posible
            for($nro=0; $nro<$m-$n+1; $nro++)
            {
                // Desde donde arranca ese elemento
                $desde = $base + $posibles - combinatoria($m - $nro, $n);
                // Hasta donde termina ese elemento
                $hasta = $base + $posibles - combinatoria($m - $nro - 1, $n) - 1; 
 
                $idx++;
                //echo "Rango: $desde - $hasta | $pos<br>";
                // Si la posicion que busco esta dentro de ese rango
                // NOTA: La segunda parte, luego del or, esta puesta como parche, pero no le encuentro logica
                if(($pos >= $desde && $pos <= $hasta) || ($hasta < $desde && $pos == $desde))
                {   
                    // Guardar el origen del grupo como punto de partida
                    $base = $desde;
                    //echo "Ok!<br>";
                    // Agregar al carton el item correspondiente.
                    $combinacion[] = $items[$idx];
                    break;
                }           
            }             
            $m--;
            $n--;          
        }
                
        return $combinacion;
    }
    //var_dump(cartones(range(0, 9), 4, 34));
    
    // Tests
    // Genero todas las combinaciones posibles de 9 elementos tomados de a 4 y los comparo con los de la funcion para ver cuales fallan
    echo "<hr>";
    $id = 0;
    $fails = 0;
    for($a=0; $a<=6; $a++)
    {            
        for($e=$a+1; $e<=9; $e++)
        {
            for($i=$e+1; $i<=9; $i++)
            {
                for($o=$i+1; $o<=9; $o++)
                {
                    $carton = cartones(range(0, 9), 4, $id);
                    if($carton[0] != $a || $carton[1] != $e || $carton[2] != $i || $carton[3] != $o)
                    {                        
                        echo "$id -> [$a, $e, $i, $o] -> [$carton[0], $carton[1], $carton[2], $carton[3]]<br>";
                        $fails++;
                    }
                    else
                    {
                        //echo "$id -> Ok!<br>";                        
                    }
                    $id++;
                }
            }
        }
    }
    
    echo "Terminado! $fails Fallas";
 

Para que todo ande los test no deberia fallar ninguno, pero actualmente fallan 140 de 210.
No encuentro como hacerlo andar

[hhs]

NSD no he visto a detalle el algoritmo pero estas usando las reglas del bingo tradicional ?

[MMan]

tal vez...

agregar 2 campos a "cartones"

1 boolean yausado
1 string numerosdelcarton

:: ni siquiera necesitarias tener un campo por cada numero... haciendo un EXPLODE("," , numerosdelcarton ) tendrias un array con todos los nums

el boolean te permite filtrar los ya usados, para obtener un nuevo carton

numerosdelcarton: guardas los numeros ORDENADOS separados con coma (o lo que sea) como un string.... esto te permite buscar el carton mas facil ( en vez de estar creando arrays/ conjuntos e iterando por cada uno de los 15 numeros )


------------
<?php

Código PHP:

function dameListaNum($cuantos=15, $min=0, $max=99){
    if ($cuantos > ($max-$min) ) {die( "error, parametros incorrectos"); }
    // si $cuantos > numero de permutaciones que se pueden hacer... die ("error, $cuantos > a lo permitido")
    
    
    $x=0;
    $valores = array();
    while ($x<$cuantos) {
      $num_aleatorio = rand($min,$max);
      if (!in_array($num_aleatorio,$valores)) {
        array_push($valores,$num_aleatorio);
        $x++;
      }
    }
 
    // ordena
    asort($valores);
    return implode(",", $valores);
}
 
// genero 1000 cartones de prueba
$cartones = array();
 
for($i=1;$i<=1000;$i++){
    $uncarton = dameListaNum();
    if (!in_array($uncarton, $cartones)){
        array_push($cartones,$uncarton);
    }
}
 
 
// prueba pa ver si hay duplicados
echo count($cartones);
echo "\n";
// elimino duplicados
$resultado = array_unique($cartones);
echo count($resultado);
// deberia dar 1000 / 1000
 

?>

[NSD]

Al fin logre hacerlo andar tras mucha horas sin dormir y varias tasas de cafe!!

Gracias por la ayuda, tratare de explicar como lo resolví para que si alguien mas tiene el mismo problema le sirva de ayuda.

Tanto los algoritmos de @informacionsys como el de @MMan y el sugerido por @pateketrueke y también la solución 1 propuesta en el primer mensaje tienen el mismo gran problema:
Para generar un cartón nuevo, necesitan conocer a los que ya están generados previamente, y, como previamente puede haber hasta 253338471349989000 combinaciones, claro esta que no hay server que soporte levantar todas esas combinaciones a memoria en simultaneo.

La solución que diseñe es la siguiente:

1) Supongamos (hipotéticamente, ya dije que no es posible) que pudiéramos crear un array que contenga las 253338471349989000 combinaciones posibles, a cada una, le correspondería un indice numérico correlativo que la identificaría dentro del array.

2) Supongamos también, que a esa lista de combinaciones la pudiera "desordenar" o "ordenar aleatoriamente" en base a una semilla (seed) de forma tal, que cada vez que la genere, este siempre en el mismo orden.

3) Cada cliente tiene un ID autoincrementado único en la base de datos, que se podría corresponder con los indices de la lista de combinaciones ordenada aleatoriamente.

4) Afirmemos que se puede obtener la combinación de una posición de la lista, sin generar a todas las demás combinaciones, es decir, obtener una combinación sin conocer a la lista completa.

5) El resultado, es que cada alta de un nuevo cliente, lleva asociada una combinación de números aleatoria (que seria el cartón del bingo que le corresponde) única, sin mas requisitos que tener un campo autoincremental como clave primaria.

6) Para desordenar la lista, el algoritmo de fisher-yates (comúnmente usado para la reproducción de listas de canciones aleatoriamente y sin repetición) con semilla, es la solución genial.

7) El código de la solución comentado:

Código PHP:

<?php
    class Factorial
    {
        /*/
         * Factoriales previamente calculados, como siempre se usan los mismos
         * y ademas son pocos, no hace falta recalcularlos todo el tiempo.
        /*/
        private static $cache = [];
        
        /*/
         * Calcular el factorial de un numero si no esta cacheado.
        /*/
        public static function calc($nro) {
            
            if(!array_key_exists($nro, self::$cache))
            {
                self::$cache[$nro] = 1;
                $numero = $nro;
                while($numero >= 1 && (self::$cache[$nro] *= $numero--));                
            }
            
            return self::$cache[$nro];
        }
    }
 
    /*/
     * @param $items array Los elementos que pueden componer un carton.
     * @param $cantidad int La cantidad de elementos por carton.
     * @param $posicion_buscada int La posicion o numero de carton buscada.
    /*/
    function carton($items, $cantidad, $posicion_buscada)
    {        
        // Una semilla constante, permite desordenar siempre de la misma manera.
        mt_srand(123456789);
        
        // Recorrer los todos elementos.
        for($posicion=count($items)-1; $posicion; $posicion--)
        {
            // Realizar los intercambios.
            $posicion_nueva = mt_rand(0, $posicion);
            $backup = $items[$posicion];
            $items[$posicion] = $items[$posicion_nueva];
            $items[$posicion_nueva] = $backup;
        }
        unset($posicion, $posicion_nueva, $backup);
        
        // Variables de uso general.
        $carton = [];
        $items_count = count($items);
        $posicion_actual = 0;
        
        // Para cada elemento que tengo que agregar al carton.
        for($elemento=0; $elemento<$cantidad; $elemento++)
        {
            // Variables para uso de cada elemento en particular.
            $items_count_combinacion = $items_count;
            $items_count_avaible = $items_count - $cantidad + $elemento;            
            $cantidad_elementos = $cantidad - $elemento;            
            $posicion_tope = $posicion_actual;
            
            // Recorrer cada item disponible.
            for($item_numero = 0; $item_numero<=$items_count_avaible; $item_numero++)
            {
                $mc = $items_count_combinacion - $item_numero - 1;
                $nc = $cantidad_elementos - 1;  
                // Hasta que posicion le corresponde este elemento.
                $posicion_tope += (Factorial::calc($mc) / (Factorial::calc($nc) * Factorial::calc($mc - $nc)));
                $item = array_shift($items);
                $items_count--;
                
                // Si la posicion buscada es menor al tope que le corresponde al elemento.
                if($posicion_buscada <= $posicion_tope)
                {
                    // Asignar el elemento al carton.
                    $carton[] = $item;
                    break;
                }
                else // Seguir buscando desde el tope en adelante.
                    $posicion_actual = $posicion_tope;
            }
        }
        
        // El carton vuelve ordenado.
        sort($carton);
        
        return $carton;
    }
    
    // Test: Generar los primeros 100 cartones.
    $cartones = [];
    $items = range(0, 99);    
    for($idx=1; $idx<=100; $idx++)
        $cartones[] = implode(", ", carton($items, 15, $idx));
    var_dump($cartones);
 

[NSD]

Una versión mejorada de ese algoritmo se puede lograr cambiando esta linea:

Código PHP:

mt_srand(123456789);
 

por esta:

Código PHP:

mt_srand($posicion_buscada);
 

y eliminando el sort del final.

Sera necesario ademas, guardar la combinación generada en la base de datos y el proceso de alta de clientes debera constar de los siguientes pasos:

1) Se da de alta un cliente con ID autoincremental.
2) Se calcula el cartón de ese cliente y se verifica que no este asignado a otro cliente previo.
3) Si no esta asignado, se guardan los datos del cartón asignándoselo al cliente.
4) Si ya esta guardado, se borra de la base de datos el cliente y se da nuevamente de alta (para que tenga un nuevo id) y se vuelve al paso 2.
5) En las lecturas se toman los datos del cartón directamente desde la base de datos.

Ventajas de esta versión mejorada:
- Mayor aleatoriedad, cartones contiguos son mas diferentes entre si.
- Menor consumo y mas velocidad, solo se calcula el carton al momento del alta.

- Contras de la versión mejorada:
- Requiere mas espacio en la base de datos.
- Posibilidad infima pero existente de que queden huecos en los id de los clientes.

Es posible, aunque extremadamente improbable, que la combinación de una semilla (que es la posición buscada) y la combinación a obtener de esa posición, coincidan con otra posición y otra combinación, por tal motivo, se debe preveer este caso con el paso 4.
Es algo muy poco probable pero que quizás alguna vez ocurra.

La versión del mensaje anterior no tiene fallas posibles y es 100% confiable, esta versión mejorada en cambio, tiene un caso particular que hay que considerar, pero las ventajas de usarla lo compensan con creces.

[NSD]

Revivo el tema porque me llego un mensaje privado con la siguiente consulta:

¿Cual es el objetivo de la posición tope? De acuerdo a si la posición tope es menor o no a la posición del cartón dentro del array, vos buscas un nuevo numero para componer el cartón.
La parte del código a la que me refiero es la siguiente:

Código PHP:

$mc = $items_count_combinacion - $item_numero - 1; 
$nc = $cantidad_elementos - 1;  
// Hasta que posición le corresponde este elemento. 
$posicion_tope += (Factorial::calc($mc) / (Factorial::calc($nc) * Factorial::calc($mc - $nc))); 
 
if($posicion_buscada <= $posicion_tope) 
{ 
...
 

El algoritmo funciona basado en combinaciones, consideremos un caso base para entenderlo mejor:
Supongamos que tienes los numero comprendidos entre el 1 y el 5 y quieres generar cartones con 3 numeros, solo podrias generar 10 cartones, puesto que la formula de combinacion es:
((m!) / (n! * (m-n)!)) = x
por lo tanto:
((5!) / (3! * (5-3)!)) = 10
Ahora bien, si quisieras generar todas las combinaciones posibles de forma "natural" tomarias el primer elemento y lo combinarias con todos los posibles:
[01]: 1, 2, 3
[02]: 1, 2, 4
[03]: 1, 2, 5
[04]: 1, 3, 4
[05]: 1, 3, 5
[06]: 1, 4, 5
Luego harias lo mismo con el segundo:
[07]: 2, 3, 4
[08]: 2, 3, 5
[09]: 2, 4, 5
Y con el tercero:
[10]: 3, 4, 5
Con el cuarto y quinto ya no hay ninguna combinacion posible para hacer sin repetir las anteriores.

Si en la funcion "carton" comentas esta parte del codigo:

Código PHP:

// Recorrer los todos elementos.
//for($posicion=count($items)-1; $posicion; $posicion--)
//{
//    // Realizar los intercambios.
//    $posicion_nueva = mt_rand(0, $posicion);
//    $backup = $items[$posicion];
//    $items[$posicion] = $items[$posicion_nueva];
//    $items[$posicion_nueva] = $backup;
//}
//unset($posicion, $posicion_nueva, $backup);
 

Y la llamas asi:

Código PHP:

$items = range(1, 5);
for($nro=1; $nro<=10; $nro++) {
  echo "[$nro]: ".implode(", ", carton($items, 3, $nro))."<br>";
}
 

Obtendras justamente ese mismo listado.

Observa que en cada posicion de numero dentro del carton (primera, segunda y tercera) en el orden listado son siempre crecientes hacia abajo y hacia la derecha, eso es muy importante.

Ahora bien, supongamos que quieres la combinacion 8:

Código PHP:

echo "[8]: ".implode(", ", carton($items, 3, 8))."<br>";
 

Que es:

[08]: 2, 3, 5

Para saber cuales son los numeros que la componen y teniendo en cuenta el punto anterior, debemos encontrar para cada numero posible (1, 2, 3, 4, 5) cual es la posicion tope en la que aparece, puedes agregar un echo antes en este lugar para observar como funciona:

Código PHP:

// Hasta que posicion le corresponde este elemento.
$posicion_tope += (Factorial::calc($mc) / (Factorial::calc($nc) * Factorial::calc($mc - $nc)));
$item = array_shift($items);
$items_count--;
 
echo "Item: $item; Tope: $posicion_tope; Buscada: $posicion_buscada;<br>";
 
// Si la posicion buscada es menor al tope que le corresponde al elemento.
if($posicion_buscada <= $posicion_tope)
{
 

Para entender mejor que es lo que esta haciendo voy a comentar cada linea de la salida:
Item: 1; Tope: 6; Buscada: 1; // Hasta la combinacion 6 tienen un 1 como primer elemento.
Item: 2; Tope: 3; Buscada: 1; // Hasta la combinacion 3 tienen un 2 como segundo elemento.
Item: 3; Tope: 1; Buscada: 1; // Hasta la combinacion 1 tienen un 3 como tercer elemento.
[1]: 1, 2, 3 // La combinacion 1 se forma con los items donde Buscada <= Tope.
Item: 1; Tope: 6; Buscada: 2; // Hasta la combinacion 6 tienen un 1 como primer elemento.
Item: 2; Tope: 3; Buscada: 2; // Hasta la combinacion 3 tienen un 2 como segundo elemento.
Item: 3; Tope: 1; Buscada: 2; // Hasta la combinacion 1 tienen un 3 como tercer elemento.
Item: 4; Tope: 2; Buscada: 2; // Hasta la combinacion 2 tienen un 4 como tercer elemento.
[2]: 1, 2, 4 // La combinacion 2 se forma con los items donde Buscada <= Tope.
Item: 1; Tope: 6; Buscada: 3; // Hasta la combinacion 6 tienen un 1 como primer elemento.
Item: 2; Tope: 3; Buscada: 3; // Hasta la combinacion 3 tienen un 2 como segundo elemento.
Item: 3; Tope: 1; Buscada: 3; // Hasta la combinacion 1 tienen un 3 como tercer elemento.
Item: 4; Tope: 2; Buscada: 3; // Hasta la combinacion 2 tienen un 4 como tercer elemento.
Item: 5; Tope: 3; Buscada: 3; // Hasta la combinacion 3 tienen un 5 como tercer elemento.
[3]: 1, 2, 5 // La combinacion 3 se forma con los items donde Buscada <= Tope.
// ...

Y asi sigue de la misma manera con los demas.