Algoritmo de torneos por eliminatorias

imagen principal Fecha de publicación: 01/12/2014

Algoritmo al cual le introduciremos unos datos con unas puntuaciones y nos devolverá los cruces en formato de torneo por eliminatorias o eliminación directa.

Utilizaremos un modelo para la inserción de los datos.

application/models/mtorneos.php

<?php
class MTorneos extends CI_Model {
    function __construct()
    {
        parent::__construct();
    }
    private $obj=array();
    public function limpiar(){
        $this->obj=array();
    }
    public function anyadir($id,$nombre,$puntos){
        $this->obj[]=array('id'=>$id,'nombre'=>$nombre,'puntos'=>$puntos);
    }
    public function ordenar(){
        $n=count($this->obj);
        if ($n>0){
            for($i=0;$i<$n-1;$i++){
                $posmin=$i;
                for($j=$i+1;$j<$n;$j++){
                    if ($this->obj[$j]["puntos"]>$this->obj[$posmin]["puntos"]){
                        $posmin=$j;
                    }
                }
                $iaux=array();
                $iaux=array('id'=>$this->obj[$i]["id"],'nombre'=>$this->obj[$i]["nombre"],'puntos'=>$this->obj[$i]["puntos"]);
                $this->obj[$i]=array('id'=>$this->obj[$posmin]["id"],'nombre'=>$this->obj[$posmin]["nombre"],'puntos'=>$this->obj[$posmin]["puntos"]);
                $this->obj[$posmin]=array('id'=>$iaux["id"],'nombre'=>$iaux["nombre"],'puntos'=>$iaux["puntos"]);
            }
        }
    }
    public function generar(){
        $matriz=array();
        $total=count($this->obj);
        if ($total>0){
            $n=log($total, 2);
            $nrondas=intval($n);
            if ($n!=$nrondas){
                $nrondas++;
            }
            $m=pow(2,$nrondas);
            $this->rellenar_resto($m-$total);
            $orden=$this->devolver_orden($m);
            foreach($orden as $r){
                $matriz[]=array('id'=>$this->obj[$r]["id"],'nombre'=>$this->obj[$r]["nombre"],'puntos'=>$this->obj[$r]["puntos"],'posicion'=>$r+1);
            }
        }
        return $matriz;
    }
    private function rellenar_resto($n){
        for($i=0;$i<$n;$i++){
            $this->obj[]=array('id'=>0,'nombre'=>'Ordenador','puntos'=>0);
        }
    }
    private function devolver_orden($n){
        $a[1]=0;
        $a[2]=$n-1;
        $v=$n;
        while(count($a)<$n){
            $v=$v/2;
            $aux=count($a);
            $x=$aux;
            for($i=$aux+1;$i<=$aux*2;$i++){
                if ($i%2!=0){
                    $a[$i]=$a[$x]-$v+1;
                }else{
                    $a[$i]=$a[$x]+$v-1;
                }
                $x--;
            }
        }
        return $a;
    }
}
?>

1) Inserción de elementos

Para introducir los elementos utilizaremos la funcion anyadir

anyadir(id, nombre, puntos)

Ejemplo:

$this->load->model('mtorneos','',TRUE);
$this->mtorneos->limpiar();

$this->mtorneos->anyadir(8,'Alicia',1);
$this->mtorneos->anyadir(2,'David',9);
$this->mtorneos->anyadir(4,'Lucía',7);
$this->mtorneos->anyadir(5,'Paula',6);
$this->mtorneos->anyadir(3,'Alberto',8);
$this->mtorneos->anyadir(6,'Oscar',5);
$this->mtorneos->anyadir(1,'Sandra',10);
$this->mtorneos->anyadir(7,'José',3);
$this->mtorneos->anyadir(9,'Pedro',11);
$this->mtorneos->anyadir(10,'Sancho',2);

2) Ordenación de elementos

Si los puntos de los elementos los introducimos desordenados tendremos que llamar a la función ordenar.

$this->mtorneos->ordenar();

En cambio si los precios de los elementos ya los introducimos de mayor a menor no hará falta llamar a esta función. Ejemplo: Pedro (Puntos:11), Sandra (Puntos:10), David (Puntos:9), etc...

3) Matriz de Resultados

Por último, sólo falta ejecutar la función generar la cual nos devolverá una matriz con los cruces establecidos, dependiendo de los puntos de cada elemento.

$t=$this->mtorneos->generar();

4) Ejemplo

$this->load->model('mtorneos','',TRUE);
$this->mtorneos->limpiar();

$this->mtorneos->anyadir(8,'Alicia',1);
$this->mtorneos->anyadir(2,'David',9);
$this->mtorneos->anyadir(4,'Lucía',7);
$this->mtorneos->anyadir(5,'Paula',6);
$this->mtorneos->anyadir(3,'Alberto',8);
$this->mtorneos->anyadir(6,'Oscar',5);
$this->mtorneos->anyadir(1,'Sandra',10);
$this->mtorneos->anyadir(7,'José',3);
$this->mtorneos->anyadir(9,'Pedro',11);
$this->mtorneos->anyadir(10,'Sancho',2);

$this->mtorneos->ordenar();
$t=$this->mtorneos->generar();
echo "<pre>";
print_r($t);
echo "</pre>";

El resultado de este ejemplo sería este:

Array
(
    [0] => Array
        (
            [id] => 9
            [nombre] => Pedro
            [puntos] => 11
            [posicion] => 1
        )

    [1] => Array
        (
            [id] => 0
            [nombre] => Ordenador
            [puntos] => 0
            [posicion] => 16
        )

    [2] => Array
        (
            [id] => 10
            [nombre] => Sancho
            [puntos] => 2
            [posicion] => 9
        )

    [3] => Array
        (
            [id] => 7
            [nombre] => José
            [puntos] => 3
            [posicion] => 8
        )

    [4] => Array
        (
            [id] => 4
            [nombre] => Lucía
            [puntos] => 7
            [posicion] => 5
        )

    [5] => Array
        (
            [id] => 0
            [nombre] => Ordenador
            [puntos] => 0
            [posicion] => 12
        )

    [6] => Array
        (
            [id] => 0
            [nombre] => Ordenador
            [puntos] => 0
            [posicion] => 13
        )

    [7] => Array
        (
            [id] => 3
            [nombre] => Alberto
            [puntos] => 8
            [posicion] => 4
        )

    [8] => Array
        (
            [id] => 2
            [nombre] => David
            [puntos] => 9
            [posicion] => 3
        )

    [9] => Array
        (
            [id] => 0
            [nombre] => Ordenador
            [puntos] => 0
            [posicion] => 14
        )

    [10] => Array
        (
            [id] => 0
            [nombre] => Ordenador
            [puntos] => 0
            [posicion] => 11
        )

    [11] => Array
        (
            [id] => 5
            [nombre] => Paula
            [puntos] => 6
            [posicion] => 6
        )

    [12] => Array
        (
            [id] => 6
            [nombre] => Oscar
            [puntos] => 5
            [posicion] => 7
        )

    [13] => Array
        (
            [id] => 8
            [nombre] => Alicia
            [puntos] => 1
            [posicion] => 10
        )

    [14] => Array
        (
            [id] => 0
            [nombre] => Ordenador
            [puntos] => 0
            [posicion] => 15
        )

    [15] => Array
        (
            [id] => 1
            [nombre] => Sandra
            [puntos] => 10
            [posicion] => 2
        )

)

Si te gusta este artículo compártelo en las redes sociales

Comentarios

No se han publicado comentarios

Publicar un comentario

Introduzca un comentario

Nombre:
Comentario:
Introduce los números
de la imagen de arriba
Introducir

Si te gusta o te es útil esta página puedes hacer una donación para permitir su mantenimiento