- Generazione di tutte le combinazioni dagli elementi che devono essere scelti in sequenza

Question

Sto cercando di scoprire se esiste già un particolare algoritmo. Voglio usarlo in un'applicazione, ma ho anche visto questo anche in alcuni problemi Project Euler.

Sto cercando di calcolare un tipo specifico di set permutazione/uscita, in cui l'elemento successivo scelto deve essere impostato su da un insieme finito di opzioni solo nella seguente serie.

Ad esempio, dire che ho 3 matrici

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

che sto cercando di generare tutte le possibilità di una sequenza contenente al massimo 1 elemento da ogni array, scelti per. Vale a dire come output, mi piacerebbe vedere:

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 

Cercare di implementare l'algoritmo in PHP o Javascript. In sostanza passerà attraverso un numero variabile di matrici che contengono un numero variabile di elementi e produrrà tutte le possibilità di sequenze che possono verificarsi in ordine sequenziale.

Esiste?

Se sì, come si chiama? Tecnicamente questa non è una permutazione o una combinazione di ciò che so su entrambi.

EDIT: Daniel Fischer mi ha informato che questo è un prodotto cartesiano, qui è un'implementazione 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

E 'un prodotto cartesiano, se esattamente un oggetto viene scelto da ciascuna lista/array, più precisamente un elenco degli elementi del prodotto cartesiano. Per gli elenchi, è nella libreria standard di Haskell:

Penso che per PHP o Javascript, devi codificarlo da solo.

Answer 2

È possibile passare attraverso gli elementi in un ciclo. Ad esempio, è possibile effettuare le seguenti operazioni per il vostro 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 però che questo è piuttosto lento, soprattutto se hai un sacco di array di array molto lunghi. Per Project Euler, di solito c'è qualche altra informazione che puoi usare invece di enumerare tutto.

Answer 3

Penso che tu abbia ragione che non è né una permutazione né una combinazione perché la lunghezza della stringa è fissa nel tuo caso. Perdonate il mio uso di java [7], ma è quello che attualmente conosco meglio.

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

In Mathematica questo è nativamente implementato come 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}}

Può anche essere fatto con Outer (prodotto generalizzata esterno):

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

O con iterazione (Table):

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

O con la ricorsione:

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

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