Múltiples foreach con más de 37 millones de posibilidades

Question

Se me ha encomendado la tarea de crear una lista de todas las posibilidades utilizando datos en 8 bloques.

Los 8 bloques tienen el siguiente número de posibilidades:

*Block 1: 12 possibilities 
*Block 2: 8 possibilities 
*Block 3: 8 possibilities 
*Block 4: 11 possibilities 
*Block 5: 16 possibilities 
*Block 6: 11 possibilities 
*Block 7: 5 possibilities 
*Block 8: 5 possibilities 

Esto da un número potencial de 37,171,200 posibilidades.

He intentado simplemente haciendo y que limita únicamente a la visualización de los valores devueltos con la longitud de cadena correcta de este modo:

foreach($block1 AS $b1){ 
    foreach($block2 AS $b2){ 
     foreach($block3 AS $b3){ 
      foreach($block4 AS $b4){ 
       foreach($block5 AS $b5){ 
        foreach($block6 AS $b6){ 
         foreach($block7 AS $b7){ 
          foreach($block8 AS $b8){ 
           if (strlen($b1.$b2.$b3.$b4.$b5.$b6.$b7.$b8) == 16) 
           { 
            echo $b1.$b2.$b3.$b4.$b5.$b6.$b7.$b8.'<br/>'; 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
} 

Sin embargo, el tiempo de ejecución era demasiado tiempo para calcular. Me preguntaba si alguien sabía de una forma más simple de hacer esto.

Answer 1

Puede mejorar su algoritmo guardando en caché los prefijos de cadena y recordando sus longitudes. Entonces no tienes que hacer eso para cada combinación.

$len = 16: 

// array for remaining characters per level 
$r = array($len); 
// array of level parts 
$p = array(); 
foreach ($block1 AS &$b1) { 
    // skip if already too long 
    if (($r[0] - strlen($b1)) <= 0) continue; 
    $r[1] = $r[0] - strlen($b1); 
    foreach ($block2 AS &$b2) { 
     if (($r[1] - strlen($b2)) <= 0) continue; 
     $r[2] = $r[1] - strlen($b2); 
     foreach ($block3 AS $b3) { 
      // … 
      foreach ($block8 AS &$b8) { 
       $r[8] = $r[7] - strlen($b8); 
       if ($r[8] == 0) { 
        echo implode('', $p).'<br/>'; 
       } 
      } 
     } 
    } 
} 

Además, el uso de referencias en foreach dejará de PHP utilizando una copia de la matriz interna.

Answer 2

Si puede expresar esto como una matriz anidada, probar un RecursiveIteratorIterator, http://php.net/manual/en/class.recursiveiteratoriterator.php

Answer 3

Se podría tratar de almacenar la parte precomputed la cadena concatenada conocido en cada una de las lelels anteriores para su posterior reutilización, evitando la concatenación de todo en el lazo más interno

foreach($block7 AS $b7){ 
    $precomputed7 = $precomputed6.$b7 
    foreach($block8 AS $b8){ 
     $precomputed8 = $precomputed7.$b8 
     if (strlen($precomputed8) == 16) { 
      echo $precomputed8.'<br/>'; 
     } 
    } 
} 

Haciendo esto análogamente para los niveles precedentes. Entonces podría tratar de probar en uno de los niveles de bucle más altos para las cadenas que ya son más largas como 16 caracteres. Puede atajar y evitar probar otras posibilidades. Pero ten cuidado, el cálculo de la longitud de la cuerda cuesta mucho rendimiento, tal vez la última mejora no valga nada, dependiendo de los datos de entrada.

Otra idea es precalcular las longitudes de cada bloque y luego recursivas en la matriz de longitudes, calcular las sumas debe ser más rápido que concatenar y calcular la longitud de las cadenas. Para el Vector de índices que coinciden con la longitud de 16, puede generar fácilmente la cadena concatenada completa.

Answer 4

Dado que tiene ese requisito de longitud de 16 y suponiendo que cada (i) posibilidad en cada uno de los bloques (b) tiene la longitud x_i_b, puede obtener una reducción que en algunos casos es imposible.

Por ejemplo, digamos que tenemos requisito de longitud 16, pero sólo los 4 bloques, con posibilidades con longitudes indicadas

Bloque 1: [2,3,4] block2: [5,6,7] Bloque 3: [8,9,10] block4: [9,10,11]

Entonces todas las posibilidades son imposibles ya que las longitudes del bloque 4 son demasiado grandes para permitir que cualquier combinación de bloques 1 - 3 compongan el resto del 16.

Ahora, si tu longitud es realmente 16, significa que tus (posibles) longitudes sonaron e de 1 a 9, suponiendo que no hay 0 longitudes.

puedo ver dos formas de abordar este:

1. Greedy
2. programación dinámica

Quizás incluso combinarlos. Para el enfoque Codicioso, escoge la posibilidad más grande en todos los bloques, luego el siguiente más grande, etc., sigue hasta cruzar el umbral de 16. Si obtuviste todos los bloques, entonces puedes emitir ese.

Ya sea que hayas alcanzado el umbral o no, puedes repetir las posibilidades.

El appraoch dinámico significa que debe almacenar algunos de los resultados que ya computa. Al igual que una selección de algunos de los bloques que le da una longitud de 7, no necesita volver a calcular eso en el futuro, pero puede recorrer los bloques restantes para ver si puede encontrar una combinación para darle lenth 9.

EDIT: Esto es algo así como el problema de la mochila pero con la restricción adicional de 1 opción por bloque por instancia. De todos modos, en términos de otras optimizaciones, definitivamente preprocesamos los bloques en matrices de longitudes solamente y mantenemos una suma en ejecución en cada nivel de iteración. Entonces solo haces 1 suma por cada iteración de cada ciclo, en lugar de 8 sumas por cada iteración. También solo str concat si necesita emitir la selección.

Si no desea una solución general (probablemente más fácil si no), puede codificar manualmente una gran cantidad de aceleraciones específicas de instancia de problema excluyendo la combinación de longitudes más grande y pequeña (y todas las selecciones menores que esa) y excluyendo la combinación de longitudes más pequeña y demasiado grande (y todas las selecciones son más grandes).