Ottieni tutte le permutazioni di un array PHP?

Question

Dato un array PHP di stringhe, per es .:

['peter', 'paul', 'mary'] 

Come generare tutte le possibili permutazioni di elementi di questo array? cioè .:

peter-paul-mary 
peter-mary-paul 
paul-peter-mary 
paul-mary-peter 
mary-peter-paul 
mary-paul-peter 

Answer 1

function pc_permute($items, $perms = array()) { 
    if (empty($items)) { 
     echo join(' ', $perms) . "<br />"; 
    } else { 
     for ($i = count($items) - 1; $i >= 0; --$i) { 
      $newitems = $items; 
      $newperms = $perms; 
      list($foo) = array_splice($newitems, $i, 1); 
      array_unshift($newperms, $foo); 
      pc_permute($newitems, $newperms); 
     } 
    } 
} 

$arr = array('peter', 'paul', 'mary'); 

pc_permute($arr); 

o

function pc_next_permutation($p, $size) { 
    // slide down the array looking for where we're smaller than the next guy 
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { } 

    // if this doesn't occur, we've finished our permutations 
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1) 
    if ($i == -1) { return false; } 

    // slide down the array looking for a bigger number than what we found before 
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { } 

    // swap them 
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp; 

    // now reverse the elements in between by swapping the ends 
    for (++$i, $j = $size; $i < $j; ++$i, --$j) { 
     $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp; 
    } 

    return $p; 
} 

$set = split(' ', 'she sells seashells'); // like array('she', 'sells', 'seashells') 
$size = count($set) - 1; 
$perm = range(0, $size); 
$j = 0; 

do { 
    foreach ($perm as $i) { $perms[$j][] = $set[$i]; } 
} while ($perm = pc_next_permutation($perm, $size) and ++$j); 

foreach ($perms as $p) { 
    print join(' ', $p) . "\n"; 
} 

http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

Answer 2

avevo bisogno di qualcosa di simile e ho trovato questo post mentre guardando. Atterrato a scrivere il seguente che fa il lavoro.

Con 8 articoli funziona in modo abbastanza veloce (un po 'più veloce degli esempi che ho trovato online), ma va oltre e il tempo di accelerazione sale rapidamente. Se hai solo bisogno di produrre i risultati, potrebbe essere reso più veloce e l'uso della memoria ridotto in modo massiccio.

print_r(AllPermutations(array('peter', 'paul', 'mary'))); 

function AllPermutations($InArray, $InProcessedArray = array()) 
{ 
    $ReturnArray = array(); 
    foreach($InArray as $Key=>$value) 
    { 
     $CopyArray = $InProcessedArray; 
     $CopyArray[$Key] = $value; 
     $TempArray = array_diff_key($InArray, $CopyArray); 
     if (count($TempArray) == 0) 
     { 
      $ReturnArray[] = $CopyArray; 
     } 
     else 
     { 
      $ReturnArray = array_merge($ReturnArray, AllPermutations($TempArray, $CopyArray)); 
     } 
    } 
    return $ReturnArray; 
} 

Si noti che il numero di permutazioni è il fattoriale del numero di elementi nell'array. Per 3 articoli ci sono 6 permutazioni, per 4 ci sono 24, per 5 ci sono 120, per 6 ci sono 720, ecc.

Answer 3

Questo fa quello che ti serve, sul posto, cioè senza allocare alcuna memoria aggiuntiva. Memorizza le permutazioni risultanti l'array $ results. Sono abbastanza fiducioso che questo è il modo digiuno per risolvere il problema.

<?php 
function computePermutations($array) { 
    $result = []; 

    $recurse = function($array, $start_i = 0) use (&$result, &$recurse) { 
     if ($start_i === count($array)-1) { 
      array_push($result, $array); 
     } 

     for ($i = $start_i; $i < count($array); $i++) { 
      //Swap array value at $i and $start_i 
      $t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t; 

      //Recurse 
      $recurse($array, $start_i + 1); 

      //Restore old order 
      $t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t; 
     } 
    }; 

    $recurse($array); 

    return $result; 
} 


$results = computePermutations(array('foo', 'bar', 'baz')); 
print_r($results); 

Questo funziona in PHP> 5.4. Ho usato una funzione anonima per la ricorsione per mantenere l'interfaccia della funzione principale pulita.

Answer 4

ho ampliato un po 'sulla risposta di Jack

function pc_permute($items, $perms = [],&$ret = []) { 
    if (empty($items)) { 
     $ret[] = $perms; 
    } else { 
     for ($i = count($items) - 1; $i >= 0; --$i) { 
      $newitems = $items; 
      $newperms = $perms; 
      list($foo) = array_splice($newitems, $i, 1); 
      array_unshift($newperms, $foo); 
      $this->pc_permute($newitems, $newperms,$ret); 
     } 
    } 
    return $ret; 
} 

Questo effettivamente restituire un array con tutte le possibili permutazioni.

$options = ['startx','starty','startz','endx','endy','endz']; 
$x = $this->pc_permute($options); 
var_dump($x); 

    [0]=> 
array(6) { 
    [0]=> 
    string(6) "startx" 
    [1]=> 
    string(6) "starty" 
    [2]=> 
    string(6) "startz" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [1]=> 
    array(6) { 
    [0]=> 
    string(6) "starty" 
    [1]=> 
    string(6) "startx" 
    [2]=> 
    string(6) "startz" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [2]=> 
    array(6) { 
    [0]=> 
    string(6) "startx" 
    [1]=> 
    string(6) "startz" 
    [2]=> 
    string(6) "starty" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [3]=> 
    array(6) { 
    [0]=> 
    string(6) "startz" 
    [1]=> 
    string(6) "startx" 
    [2]=> 
    string(6) "starty" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [4]=> 
    array(6) { 
    [0]=> 
    string(6) "starty" 
    [1]=> 
    string(6) "startz" 
    [2]=> 
    string(6) "startx" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [5]=> 
    array(6) { 
    [0]=> 
    string(6) "startz" 
    [1]=> 
    string(6) "starty" 
    [2]=> 
    string(6) "startx" 
    [3]=> 
    string(4) "endx" 
    [4]=> 
    string(4) "endy" 
    [5]=> 
    string(4) "endz" 
    } 
    [6]=> ................ a lot more 

Ho trovato un po 'più utile per ottenere un array indietro invece di una stringa. Poi tocca al utilizzando l'applicazione come gestire i resutls (a unirsi a loro, o altro)

Answer 5

versione semplice con la ricorsione e senza artificiali argomenti extra:

function permuteArray(array $input) { 
    $input = array_values($input); 

    // permutation of 1 value is the same value 
    if (count($input) === 1) { 
     return array($input); 
    } 

    // to permute multiple values, pick a value to put in the front and 
    // permute the rest; repeat this with all values of the original array 
    $result = []; 
    for ($i = 0; $i < count($input); $i++) { 
     $copy = $input; 
     $value = array_splice($copy, $i, 1); 
     foreach (permuteArray($copy) as $permutation) { 
      array_unshift($permutation, $value[0]); 
      $result[] = $permutation; 
     } 
    } 

    return $result; 
} 

Questo algoritmo è bello e istruttivo come si lo farebbe su carta, ma per il resto molto inefficiente in quanto calcola più volte le stesse permutazioni. Per non dire che è molto poco pratico per il calcolo delle permutazioni di array più grandi in quanto lo spazio e il numero di calcoli crescono esponenzialmente.