PrEDA: cálculo del elemento mayoritario de un vector

Hoy vengo a compartir un algoritmo de programación para resolver el problema de calcular el elemento mayoritario de un vector. Podemos hacerlo a lo bruto, directamente calculando cuántas veces se repite cada elemento.

Pero aquí la historia está en aplicar la estrategia de programación divide y vencerás. Si un elemento es mayoritario en un vector de n elementos, entonces se repite por lo menos n/2+1 veces. La estrategia consiste en que si un elemento es mayoritario en una mitad del vector, entonces es candidato para ser mayoritario. El problema inicial se subdivide en subproblemas hacia abajo más sencillos de resolver, para luego combinar las soluciones hacia arriba hasta llegar a la solución.

Nice coding!

El código

<?php

$numberOfItems = 10;
$minimunNumber = 1;
$maximunNumber = 2;

$array = array();
for ($i = 1; $i <= $numberOfItems; ++$i) {
    $array[$i] = rand($minimunNumber, $maximunNumber);
}

echo 'Mayority element in array('.implode(',', $array).') is: '
    .mayorityElementCalculation(1, $numberOfItems, $array)
    .PHP_EOL;

function mayorityElementCalculation($i, $j, $array)
{
    echo 'Mayority from '.$i.' to '.$j.PHP_EOL;
    if ($i == $j) {
        return $array[$i];
    } else {
        $m = intval(floor(($i + $j) / 2));
        $s1 = mayorityElementCalculation($i, $m, $array);
        $s2 = mayorityElementCalculation($m + 1, $j, $array);
        echo ' m='.$m.', s1='.$s1.', s2='.$s2.PHP_EOL;
    }
    $ret = combine($s1, $s2, $array);
    echo ' combine result = '.$ret.PHP_EOL;

    return $ret;
}

function combine($s1, $s2, $array)
{
    echo ' Combine '.$s1.'-'.$s2.PHP_EOL;
    if ($s1 == -1 and $s2 == -1) {
        return -1;
    }
    if ($s1 == -1 and $s2 != -1) {
        return checkMayority($s2, $array);
    }
    if ($s1 != -1 and $s2 == -1) {
        return checkMayority($s1, $array);
    } 
    if ($s1 != -1 and $s2 != -1) {
        if (checkMayority($s1, $array) == $s1) {
            return $s1;
        } else {
            if (checkMayority($s2, $array) == $s2) {
                return $s2;
            } else {
                return -1;
            }
        }
    }
}

function checkMayority($s, $array)
{
    $c = 0;

    for ($k = 1; $k <= count($array); ++$k) {
        if ($array[$k] == $s) {
            ++$c;
        } 
    }

    echo ' checkMayority = '.$c.PHP_EOL;

    if ($c > intval(count($array) / 2)) {
        return $s;
    } else {
        return -1;
    }
}

Este código lo puedes poner en un ficher .php y al ejecutarlo tienes que ver algo como esto: