¿Obtiene todas las permutaciones de una matriz de PHP?

Question

dado una matriz PHP de cadenas, por ejemplo .:

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

Cómo generar todas las posibles permutaciones de elementos de esta matriz? es decir .:

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

necesitaba algo similar y encontré este post mientras mira. Aterrizó escribiendo lo siguiente que hace el trabajo.

Con 8 elementos funciona bastante rápido (un poco más rápido que los ejemplos que encontré en línea), pero vaya más allá y el tiempo de ejecución aumenta rápidamente. Si solo necesita generar los resultados, podría hacerse más rápido y el uso de la memoria se reduciría de forma masiva.

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; 
} 

Tenga en cuenta que el número de permutaciones es el factorial de la cantidad de elementos en la matriz. Para 3 elementos hay 6 permutaciones, para 4 hay 24, para 5 hay 120, para 6 hay 720, etc.

Answer 3

Esto hace lo que necesita, en su lugar, es decir, sin asignar memoria adicional. Almacena las permutaciones resultantes de la matriz $ results. Estoy bastante seguro de que esta es la manera rápida de resolver la tarea.

<?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); 

Esto funciona en PHP> 5.4. Usé una función anónima para la recursión para mantener limpia la interfaz de la función principal.

Answer 4

amplié un poco en la respuesta de 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; 
} 

En realidad, esto devolverá un array con todas las permutaciones posibles.

$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 

Me pareció un poco más útil recuperar una matriz en lugar de una cadena. Luego le toca al uso de la aplicación cómo manejar los los resultados (para unirse a ellos, o algo más)

Answer 5

versión simple con la recursividad y no hay argumentos adicionales artificiales:

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; 
} 

Este algoritmo es muy agradable e instructiva cómo Lo haría en papel, pero de lo contrario sería muy ineficiente ya que calcula las mismas permutaciones varias veces. No quiere decir que no es muy práctico para calcular las permutaciones de matrices más grandes a medida que el espacio y la cantidad de cálculos crecen exponencialmente.