Algoritmo PHP para generar todas las combinaciones de un tamaño específico a partir de un solo conjunto

6 minutos de lectura

Algoritmo PHP para generar todas las combinaciones de un tamano
asim-ishaq

Estoy tratando de deducir un algoritmo que genera todas las combinaciones posibles de un tamaño específico, algo así como una función que acepta una matriz de caracteres y tamaño como su parámetro y devuelve una matriz de combinaciones.

Ejemplo: Digamos que tenemos un conjunto de caracteres: Conjunto A = {A,B,C}

a) Todas las combinaciones posibles de tamaño 2: (3^2 = 9)

AA, AB, AC
BA, BB, BC
CA, CB, CC

b) Todas las combinaciones posibles de tamaño 3: (3^3 = 27)

AAA, AAB, AAC,
ABA, ABB, ACC,
CAA, BAA, BAC,
.... ad so on total combinations = 27

Tenga en cuenta que el tamaño de la pareja puede ser mayor que el tamaño total de la población. Ex. si el conjunto contiene 3 caracteres, también podemos crear una combinación de tamaño 4.

EDITAR: También tenga en cuenta que esto es diferente de la permutación. En la permutación no podemos tener caracteres repetidos, por ejemplo, AA no puede venir si usamos el algoritmo de permutación. En estadística se le conoce como muestreo.

Algoritmo PHP para generar todas las combinaciones de un tamano
Joel Hinz

Yo usaría una función recursiva. Aquí hay un ejemplo (de trabajo) con comentarios. ¡Espero que esto funcione para usted!

function sampling($chars, $size, $combinations = array()) {

    # if it's the first iteration, the first set 
    # of combinations is the same as the set of characters
    if (empty($combinations)) {
        $combinations = $chars;
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }

    # call same function again for the next iteration
    return sampling($chars, $size - 1, $new_combinations);

}

// example
$chars = array('a', 'b', 'c');
$output = sampling($chars, 2);
var_dump($output);
/*
array(9) {
  [0]=>
  string(2) "aa"
  [1]=>
  string(2) "ab"
  [2]=>
  string(2) "ac"
  [3]=>
  string(2) "ba"
  [4]=>
  string(2) "bb"
  [5]=>
  string(2) "bc"
  [6]=>
  string(2) "ca"
  [7]=>
  string(2) "cb"
  [8]=>
  string(2) "cc"
}
*/

  • En lugar del doble foreach, también podría escribir su propia función de producto cartesiano, pero parecía exagerado para este ejemplo.

    – Joel Hinz

    28 de septiembre de 2013 a las 14:14

  • Esta no es una función iterativa. Es recursivo, ya que claramente sigue llamándose a sí mismo…

    – Irrah

    5 mayo 2014 a las 10:16

  • para aquellos que no quieren que un carácter exista más de una vez en cada combinación, cambie el último bucle foreach a: if (strpos($combination, $char) === false) {$new_combinations[] = $combinación. $char;}

    – apfz

    3 de junio de 2018 a las 16:15

  • ¿Se puede realizar esta función con la nueva versión de PHP 7.2 o no hay novedades para optimizar la función actual en la nueva versión? @JoelHinz?

    – Andreas Hunter

    15 de noviembre de 2018 a las 7:24

  • @AndreasHunter No veo ninguna razón por la que el código no funcione en PHP> = 7.2, aunque estoy seguro de que se puede optimizar; fue un ejemplo de cómo funciona, no una optimización.

    – Joel Hinz

    15 de noviembre de 2018 a las 9:04

Algoritmo PHP para generar todas las combinaciones de un tamano
Santiago Alejandro

Un posible algoritmo sería:

$array_elems_to_combine = array('A', 'B', 'C');
$size = 4;
$current_set = array('');

for ($i = 0; $i < $size; $i++) {
    $tmp_set = array();
    foreach ($current_set as $curr_elem) {
        foreach ($array_elems_to_combine as $new_elem) {
            $tmp_set[] = $curr_elem . $new_elem;
        }
    }
    $current_set = $tmp_set;
}

return $current_set;

Básicamente, lo que hará es tomar cada elemento del conjunto actual y agregar todos los elementos de la matriz de elementos.

En el primer paso: tendrás como resultado ('a', 'b', 'c')después del paso de segundos: ('aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc') y así.

  • Estoy tratando de probarlo. ¿Qué es $arra_of_elem y también en el segundo y tercer ciclo usar foreach en lugar de for

    – asim-ishaq

    28 de septiembre de 2013 a las 13:54


  • @asim-ishaq Es la matriz o conjunto donde tiene los elementos para combinar. En tu caso: Array(‘A’, ‘B’, ‘C’)

    – Santiago Alessandri

    28 de septiembre de 2013 a las 13:55

  • No funciona bien. Para cualquier tamaño genera combinaciones en tamaño 3

    – asim-ishaq

    28 de septiembre de 2013 a las 14:07


  • @asim-ishaq Acabo de probar el código anterior en escribircodeonline.com/php cambiando el retorno por un print_r y funciona bien para combinaciones de 4 elementos

    – Santiago Alessandri

    28 de septiembre de 2013 a las 14:13

1646754973 25 Algoritmo PHP para generar todas las combinaciones de un tamano
ción

Puedes hacer esto recursivamente. Tenga en cuenta que según su definición, las “combinaciones” de longitud n+1 se puede generar a partir de las combinaciones de longitud n tomando cada combinación de longitud n y agregando una de las letras de su conjunto. Si te importa, puedes probarlo inducción matemática.

Entonces, por ejemplo, con un conjunto de {A,B,C} las combinaciones de longitud 1 son:

A, B, C

Las combinaciones de longitud 2 son por lo tanto

(A, B, C) + A = AA, BA, CA
(A, B, C) + B = AB, BB, BC
(A, B, C) + C = AC, CB, CC

Este sería el código y aquí en idea

function comb ($n, $elems) {
    if ($n > 0) {
      $tmp_set = array();
      $res = comb($n-1, $elems);
      foreach ($res as $ce) {
          foreach ($elems as $e) {
             array_push($tmp_set, $ce . $e);
          }
       }
       return $tmp_set;
    }
    else {
        return array('');
    }
}
$elems = array('A','B','C');
$v = comb(4, $elems);

  • Sí, eso es correcto, pero ¿cómo se puede generalizar en un algoritmo para crear combinaciones de n tamaños?

    – asim-ishaq

    28 de septiembre de 2013 a las 13:48

  • @asim-ishaq Eso se debe al hecho de que esta propiedad que describí es válida para todos n. editaré

    – ción

    28 de septiembre de 2013 a las 13:49

Aquí hay un código hecho por un amigo, generó combinaciones únicas de números X de una lista de números.

Si tiene una lista de números, como 1,3,4,7,12, puede generar conjuntos de números X, todos únicos, no repetitivos.

La primera función funciona con PHP 7.4 o más, y la segunda usa claves para almacenar los valores. Ambos funcionan muy bien según el punto de referencia.

function get_combos74($map, $size, &$generated = [], $loop = 1, $i = 0, $prefix = [])
{
    if ($loop == 1) {
        sort($map);
    }

    for (; $i < count($map); $i++) {
        if ($loop < $size) {
            get_combos74($map, $size, $generated, $loop + 1, $i + 1, [...$prefix, $map[$i]]);
        } else {
            $generated[] = [...$prefix, $map[$i]];
        }
    }

    return $generated;
}
function get_combosSTR($map, $size, &$generated = [], $loop = 1, $i = 0, $prefix = '')
{
    if ($loop == 1) {
        sort($map);
    }

    for (; $i < count($map); $i++) {
        if ($loop < $size) {
            get_combosSTR($map, $size, $generated, $loop + 1, $i + 1, "$prefix{$map[$i]}:");
        } else {
            $generated["$prefix{$map[$i]}"] = 0;
        }
    }

    return $generated;
}

1646754974 590 Algoritmo PHP para generar todas las combinaciones de un tamano
usuario1913526

Otra idea usando conversión de base numérica

$items = ['a', 'b', 'c', 'd'];
$length = 3;
$numberOfSequences = pow(count($items), $length);
for ($i = 0; $i < $numberOfSequences; $i++) {
    $results[] = array_map(function ($key) use ($items) {
        return $items[base_convert($key, count($items), 10)];
    }, str_split(str_pad(base_convert($i, 10, count($items), $length, 0, STR_PAD_LEFT)));
}

return $results;

  • Advertencia, no debe tener más elementos en la matriz de elementos de los que pueden manejar los parámetros base_convert: y ese número es 36

    – usuario1913526

    21 de marzo de 2019 a las 14:08

  • Advertencia, no debe tener más elementos en la matriz de elementos de los que pueden manejar los parámetros base_convert: y ese número es 36

    – usuario1913526

    21 de marzo de 2019 a las 14:08

¿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