Encontrar los subconjuntos de una matriz en PHP

6 minutos de lectura

Encontrar los subconjuntos de una matriz en PHP
dtx

Tengo un esquema relacional con atributos (ABCD). También tengo un conjunto de dependencias funcionales conmigo.

Ahora necesito determinar el cierre de todos los posibles subconjuntos de atributos de R. Ahí es donde estoy atascado. Necesito aprender a encontrar subconjuntos (no repetidos) en PHP.

Mi matriz se almacena así.

$ATTRIBUTES = ('A', 'B', 'C', 'D').

entonces mis subconjuntos deberían ser

$SUBSET = ('A', 'B', 'C', 'D', 'AB', 'AC', AD', 'BC', 'BD', 'CD', 'ABC', 'ABD', 'BCD', 'ABCD')

El código no debería ser algo grande, pero por alguna razón no puedo entenderlo.

  • ¿Importa el orden? También creo que podrías tener que usar la recursividad.

    – Pwnna

    23 de mayo de 2011 a las 4:23

  • no, el orden no importa. Puedo ordenarlo por el tamaño de la cadena más tarde, solo necesito una forma de obtener los subconjuntos

    – dtx

    23 de mayo de 2011 a las 4:31

  • ¿Básicamente solo estás buscando el algoritmo de apretón de manos?

    – Pwnna

    23 de mayo de 2011 a las 4:37

  • eso es más una cuestión de conjunto de potencia. Estás pidiendo generar el conjunto de potencia de $attributes

    – fbstj

    23 de mayo de 2011 a las 4:41

  • php.net/manual/en/function.shuffle.php#88408 es un ejemplo de generador de conjunto de potencia en php

    – fbstj

    23 de mayo de 2011 a las 4:43

Deseas el conjunto de poder de $attributes? Eso es lo que implica tu pregunta.

Se puede encontrar un ejemplo aquí (citado para completar)

<?php 
/** 
* Returns the power set of a one dimensional array, a 2-D array. 
* [a,b,c] -> [ [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c] ]
*/ 
function powerSet($in,$minLength = 1) { 
   $count = count($in); 
   $members = pow(2,$count); 
   $return = array(); 
   for ($i = 0; $i < $members; $i++) { 
      $b = sprintf("%0".$count."b",$i); 
      $out = array(); 
      for ($j = 0; $j < $count; $j++) { 
         if ($b{$j} == '1') $out[] = $in[$j]; 
      } 
      if (count($out) >= $minLength) { 
         $return[] = $out; 
      } 
   } 
   return $return; 
} 

  • Genial estaba tratando de convertir esto de Java, no estaba funcionando, esto es 🙂

    – Danuof

    23 de julio de 2013 a las 22:23

  • @FallingBullets, ¿hay alguna forma de modificar esto para que devuelva repeticiones? es decir, de (1,2,3) regresa (2 3)(1 2)(1 3)(1 2 3)(1 1 2)(1 1 3)(2 2 1) etc.?

    – Jen nacido

    18 de febrero de 2014 a las 3:12

  • Técnicamente, esto genera todos los subconjuntos excepto el conjunto vacío. Solo un punto técnico: no es exactamente el conjunto de potencia de una matriz.

    – James Stott

    29 de diciembre de 2014 a las 12:27

  • Eliminar $b=sprintf(...)utilizar $i>>$j&1 en lugar de $b{$j} == '1' – más corto y más rápido.

    – Tito

    27 de mayo de 2017 a las 8:13


  • para renderizar $membersy $count obsoleto: for($i=1<<count($in);--$i;){$out=[];foreach($in as$j=>$u)if($i‌​>>$j&1)$out[]=$u​];...}. De esta manera (con $i no golpear 0), también se garantiza que $out nunca está vacío, así que si $minLength es 1no necesitas count($out) cualquiera.

    – Tito

    27 de mayo de 2017 a las 9:50


1646745729 869 Encontrar los subconjuntos de una matriz en PHP
Yada

Usando php array_merge podemos tener una buena función powerSet corta

function powerSet($array) {
    // add the empty set
    $results = [[]];

    foreach ($array as $element) {
        foreach ($results as $combination) {
            $results[] = array_merge(array($element), $combination);
        }
    }

    return $results;
}

  • Esto me ahorró más de una semana de romper el cerebro, simple y directo al grano.

    – James Bondze

    6 de diciembre de 2020 a las 17:37

Aquí una solución de retroceso.

dada una función que devuelve todos los subconjuntos de longitud L del conjunto de entrada, busque todos los subconjuntos de longitud L desde L = 2 hasta la longitud de entrada del conjunto de datos

<?php

function subsets($S,$L) {
    $a = $b = 0;
    $subset = [];
    $result = [];
    while ($a < count($S)) {
        $current = $S[$a++];
        $subset[] = $current;
        if (count($subset) == $L) {
            $result[] = json_encode($subset);
            array_pop($subset);
        }
        if ($a == count($S)) {
            $a = ++$b;
            $subset = [];
        }
    }
    return $result;
}



$S = [ 'A', 'B', 'C', 'D'];
$L = 2;


// L = 1 -> no need to do anything
print_r($S);

for ($i = 2; $i <= count($S); $i++)
    print_r(subsets($S,$i));

1646745730 433 Encontrar los subconjuntos de una matriz en PHP
walf

Según la respuesta de @Yada, esto generará el conjunto de potencia de una matriz, pero conservará las claves de la matriz original en cada subconjunto (el valor de retorno aún está indexado numérica y secuencialmente). Esto es muy útil si necesita subconjuntos de una matriz asociativa.

Los subconjuntos también conservan el orden de los elementos de la matriz original. Agregué una ordenación estable a $results porque lo necesitaba, pero puedes omitirlo.

function power_set($array) {
    $results = [[]];
    foreach ($array as $key => $value) {
        foreach ($results as $combination) {
            $results[] = $combination + [$key => $value];
        }
    }

    # array_shift($results); # uncomment if you don't want the empty set in your results
    $order = array_map('count', $results);
    uksort($results, function($key_a, $key_b) use ($order) {
        $comp = $order[$key_a] - $order[$key_b]; # change only this to $order[$key_b] - $order[$key_a] for descending size
        if ($comp == 0) {
            $comp = $key_a - $key_b;
        }
        return $comp;
    });
    return array_values($results);
}

Dada la entrada de OP, var_dump(power_set(['A', 'B', 'C', 'D'])); proporciona:

array(16) {
  [0] =>
  array(0) {
  }
  [1] =>
  array(1) {
    [0] =>
    string(1) "A"
  }
  [2] =>
  array(1) {
    [1] =>
    string(1) "B"
  }
  [3] =>
  array(1) {
    [2] =>
    string(1) "C"
  }
  [4] =>
  array(1) {
    [3] =>
    string(1) "D"
  }
  [5] =>
  array(2) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
  }
  [6] =>
  array(2) {
    [0] =>
    string(1) "A"
    [2] =>
    string(1) "C"
  }
  [7] =>
  array(2) {
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
  }
  [8] =>
  array(2) {
    [0] =>
    string(1) "A"
    [3] =>
    string(1) "D"
  }
  [9] =>
  array(2) {
    [1] =>
    string(1) "B"
    [3] =>
    string(1) "D"
  }
  [10] =>
  array(2) {
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
  [11] =>
  array(3) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
  }
  [12] =>
  array(3) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
    [3] =>
    string(1) "D"
  }
  [13] =>
  array(3) {
    [0] =>
    string(1) "A"
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
  [14] =>
  array(3) {
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
  [15] =>
  array(4) {
    [0] =>
    string(1) "A"
    [1] =>
    string(1) "B"
    [2] =>
    string(1) "C"
    [3] =>
    string(1) "D"
  }
}

Siguiendo la respuesta de @fbstj, actualizo la función:

  • Utilizar operadores bit a bit en lugar de sprintf (@Titus comenta)
  • Manejar conjunto vacío (comentarios de (@James Stott y @fbstj)
  • Actualizar sintaxis a PHP 7+
function powerSet(array $in, int $minLength = 0): array
{
    $return = [];
    
    if ($minLength === 0) {
        $return[] = [];
    }

    for ($i = 1 << count($in); --$i;) {
        $out = [];

        foreach ($in as $j => $u) {
            if ($i >> $j & 1) {
                $out[] = $u;
            }
        }

        if (count($out) >= $minLength) {
            $return[] = $out;
        }
    }
    
    return $return;
}

Dado que las funciones de ajuste de potencia pueden aumentar mucho la carga de memoria (2contar ($ en) iteraciones), considere usar Generador:

function powerSet(array $in, int $minLength = 0): \Generator
{
    if ($minLength === 0) {
        yield [];
    }

    for ($i = 1 << count($in); --$i;) {
        $out = [];

        foreach ($in as $j => $u) {
            if ($i >> $j & 1) {
                $out[] = $u;
            }
        }

        if (count($out) >= $minLength) {
            yield $out;
        }
    }
}

Uso:

foreach (powerSet(range(1, 10)) as $value) {
    echo implode(', ', $value) . "\n";
}

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad