Algoritmo: generación de todas las combinaciones de los elementos que se deben elegir en la secuencia

Question

Estoy buscando averiguar si un algoritmo en particular ya existe. Quiero usarlo en una aplicación, pero también he visto esto en varios problemas Project Euler también.

Estoy buscando para calcular un tipo específico de conjunto de permutación/salida, donde el próximo elemento elegido debe ser uno de un conjunto finito de opciones en el siguiente conjunto.

Por ejemplo, dicen que tengo 3 matrices

$a1 = array("a", "b", "c"); 
$a2 = array("d", "e", "f"); 
$a3 = array("g", "h", "i"); 

que estoy buscando para generar todas las posibilidades de una secuencia que contiene como máximo 1 elemento de cada conjunto, elegido con el fin. Es decir, como salida, me gustaría ver:

adg aeg afg 
adh aeh afh 
adi aei afi 

bdg beg bfg 
bdh beh bfh 
bdi bei bfi 

cdg ceg cfg 
cdh ceh cfh 
cdi cei cfi 

Buscando implementar el algoritmo en PHP o Javascript. En esencia, pasará por un número variable de matrices que contienen un número variable de elementos, y dará salida a todas las posibilidades de secuencias que pueden ocurrir en orden secuencial.

¿Existe esto?

Si es así, ¿cómo se llama? Técnicamente, esto no es una permutación o una combinación de lo que sé sobre ambos.

EDIT: Daniel Fischer me ha informado que este es un producto cartesiano, aquí es una implementación taken from the PHP website:

function array_cartesian_product($arrays) 
{ 
    $result = array(); 
    $arrays = array_values($arrays); 
    $sizeIn = sizeof($arrays); 
    $size = $sizeIn > 0 ? 1 : 0; 
    foreach ($arrays as $array) 
     $size = $size * sizeof($array); 
    for ($i = 0; $i < $size; $i ++) 
    { 
     $result[$i] = array(); 
     for ($j = 0; $j < $sizeIn; $j ++) 
      array_push($result[$i], current($arrays[$j])); 
     for ($j = ($sizeIn -1); $j >= 0; $j --) 
     { 
      if (next($arrays[$j])) 
       break; 
      elseif (isset ($arrays[$j])) 
       reset($arrays[$j]); 
     } 
    } 
    return $result; 
} 

Answer 1

Es un producto cartesiano, si exactamente un elemento es escogido de cada lista/matriz, más precisamente una lista de los elementos del producto cartesiano. Para las listas, está en la biblioteca estándar de Haskell:

Prelude> sequence ["abc","def","ghi"] 
["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh" 
,"bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"] 

Creo que para PHP o Javascript, tiene que codificarlo usted mismo.

Answer 2

Puede examinar los elementos en un bucle. Por ejemplo, puede hacer lo siguiente para su caso:

var ret = []; 
for (var i=0; i<a1.length; i++) { 
    for (var j=0; j<a2.length; j++) { 
    for (var k=0; k<a3.length; k++) { 
     ret.push([a1[i], a2[j], a3[k]]); 
    } 
    } 
} 
// do stuff with ret 

Nota sin embargo que esto es bastante lento, especialmente si usted tiene un montón de arreglos de arreglos muy largos. Para el Proyecto Euler, usualmente hay otra información que puede usar en lugar de enumerar todo.

Answer 3

Creo que tienes razón en que no es una permutación ni una combinación porque la longitud de la cuerda está fija en tu caso. Disculpe mi uso de Java [7], pero es el que mejor conozco actualmente.

public abstract class AFixedPermutation { 
    private char[][] fields; 
    private StringBuilder sb = new StringBuilder(); 
    private int[] callvec; 
    private int maxDepth; 

    public FixedPermutation(char[][] fields) { 
    this.fields = fields; 

    callvec = new int[fields.length]; 
    for (int i = 0; i < fields.length; i++) callvec[i] = 0; 
    maxDepth = callvec.length - 1; 
    recurse(0); 
    } 

    protected abstract emit(String s); 

    private void recurse(int depth) { 
    for (int i = 0; i < fields[depth].length; i++) { 
     callvec[depth] = i; 
     if (depth == maxDepth) { apply(); } 
     else {recurse(depth + 1); } 
    } 
    } 

    private void apply() { 
     sb.setLength(0); 
     for (int i = 0; i < callvec.length; i++) { 
     sb.append(fields[i][callvec[i]]); 
     } 
     emit(sb.toString()); 
    } 
} 

Answer 4

En Mathematica esto se implementa de forma nativa como Tuples.

Tuples[{{a, b, c}, {d, e, f}, {g, h, i}}] 

{{a, d, g}, {a, d, h}, {a, d, i}, {a, e, g}, {a, e, h}, {a, e, i}, 
{a, f, g}, {a, f, h}, {a, f, i}, {b, d, g}, {b, d, h}, {b, d, i}, 
{b, e, g}, {b, e, h}, {b, e, i}, {b, f, g}, {b, f, h}, {b, f, i}, 
{c, d, g}, {c, d, h}, {c, d, i}, {c, e, g}, {c, e, h}, {c, e, i}, 
{c, f, g}, {c, f, h}, {c, f, i}}

También se puede hacer con Outer (producto generalizada externa):

Outer[List, {a, b, c}, {d, e, f}, {g, h, i}] 

O con iteración (Table):

Table[{x, y, z}, 
{x, {a, b, c}}, 
{y, {d, e, f}}, 
{z, {g, h, i}} 
] 

O con la recursividad:

sets[{}, c__] := {{c}} 
sets[{x_, r___}, c___] := Join @@ (sets[{r}, c, #] & /@ x) 

sets[{{a, b, c}, {d, e, f}, {g, h, i}}]