Combinatoria

README.md

Juntos y revueltos

La idea es sacar todas las posibles combinaciones para un set de datos, en este caso las letras de la a-h. Queremos todos los pares, tríos, cuartetos, etcétera, en los que pueden aparecer estos elementos. Planeamos este algoritmo originalmente para poder sacar relaciones comunes entre documentos con varias etiquetas.

Combinatoria.php

<?
// Algoritmo para sacar las combinaciones de n elementos

// Los elementos que hay que combinar
$elementos = array('a','b','c','d','e','f','g','h');
$elementos_invert = array_flip($elementos);
$cuantos = count($elementos);
$corridas = array();
$resultados = $elementos;

// Por cada elemento, hay una vuelta, un nCr
for ($i=1; $i<=$cuantos; $i++) {
	
	// La primera corrida son los elementos a secas
	if (!isset($corridas[$i-1])) {
		$corridas[$i] = $elementos;
		continue;
	}
	$elementos_new = $elementos;
	
	// Las letras sobrantes
	$letras_slice = array_slice($elementos_new, ($i-1));
	$letras_rebuilt = implode("", $letras_slice);
	
	// Cada elemento de la vuelta anterior es una vuelta en esta
	foreach($corridas[$i-1] as $j=>$itera) {
		$subletras = str_split($itera);
		$subletras_c = count($subletras)-1;
		
		// Cada letra de las letras sobrantes es otra vuelta
		foreach ($letras_slice as $itera2) {
			$letra_fin = $elementos_invert[$subletras[$subletras_c]];
			$letra_coteja = $elementos_invert[$itera2];
			
			if (!in_array($itera2, $subletras) && ($letra_fin < $letra_coteja)
			) {
				$corridas[$i][] = $itera.$itera2;
				$resultados[] = $itera.$itera2;
			}
		}
	}
}
print_r($resultados);