php - permutaciones - problemas de combinatoria

Permutaciones: todos los conjuntos posibles de números

Question

Tengo números, de 0 a 8. Me gustaría obtener resultados, todos los conjuntos posibles de esos números, cada conjunto debe usar todos los números, cada número puede ocurrir solo una vez en un conjunto.

Me gustaría ver una solución hecha en PHP que pudiera imprimir el resultado. O, al menos, me gustaría un poco de refrigerio en la teoría de la combinatoria, ya que hace tiempo que lo he olvidado. ¿Cuál es la fórmula para calcular cuántas permutaciones habrá?

Conjuntos de ejemplos:

• 0-1-2-3-4-5-6-7-8
• 0-1-2-3-4-5-6-8-7
• 0-1-2-3-4-5-8-6-7
• 0-1-2-3-4-8-5-6-7
• 0-1-2-3-8-4-5-6-7
• 0-1-2-8-3-4-5-6-7
• y así...

Answer 1

Aquí está mi propuesta, espero un poco más claro que la respuesta aceptada.

   function permutate($elements, $perm = array(), &$permArray = array())
{
    if(empty($elements))
    {
       array_push($permArray,$perm); return;
    }

    for($i=0;$i<=count($elements)-1;$i++)
    {
       array_push($perm,$elements[$i]);
       $tmp = $elements; array_splice($tmp,$i,1);
       permutate($tmp,$perm,$permArray);
       array_pop($perm);
    }

    return $permArray;
}

y uso:

$p = permutate(array(''a'',''b'',''c''));
foreach($p as $perm)
    print join(",",$perm)."|/n";

Answer 2

Básicamente estás hablando de permutaciones donde tanto n como k son 9, ¡así que tendrás 9! diferentes permutaciones; mira esto: http://en.wikipedia.org/wiki/Permutation .

Answer 3

Como esta pregunta a menudo aparece en los resultados de Búsqueda de Google, aquí hay una versión modificada de la respuesta aceptada que devuelve todas las combinaciones en una matriz y las pasa como un valor de retorno de la función.

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

Usar:

$value = array(''1'', ''2'', ''3'');
print_r(pc_permute($value));

Answer 4

Desde PHP 5.5 puedes usar Generators . Los generadores ahorran mucha memoria y son mucho más rápidos (más de la mitad en comparación con pc_permute () ). Entonces, si tiene alguna posibilidad de instalar PHP 5.5, definitivamente quiere Generadores. Esta recortada se transporta desde Python: https://.com/a/104436/3745311

function permutations(array $elements)
{
    if (count($elements) <= 1) {
        yield $elements;
    } else {
        foreach (permutations(array_slice($elements, 1)) as $permutation) {
            foreach (range(0, count($elements) - 1) as $i) {
                yield array_merge(
                    array_slice($permutation, 0, $i),
                    [$elements[0]],
                    array_slice($permutation, $i)
                );
            }
        }
    }
}

Uso de muestra:

$list = [''a'', ''b'', ''c''];

foreach (permutations($list) as $permutation) {
    echo implode('','', $permutation) . PHP_EOL;
}

Salida:

a,b,c
b,a,c
b,c,a
a,c,b 
c,a,b
c,b,a

Answer 5

Está buscando la fórmula de permutaciones:

nPk = n!/(n-k)!

En tu caso, tienes 9 entradas y quieres elegir todas, ¡eso es 9P9 = 9! = 362880

Puede encontrar un algoritmo PHP para permutar en la receta 4.26 del "Cookbook PHP" de O''Reilly.

pc_permute(array(0, 1, 2, 3, 4, 5, 7, 8));

Copiado desde O''Reilly:

function pc_permute($items, $perms = array( )) {
    if (empty($items)) { 
        print join('' '', $perms) . "/n";
    }  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);
         }
    }
}

Answer 6

Esta es mi versión de clase. Esta clase crea y devuelve una matriz permutada como resultado

class Permutation {
    private $result;

    public function getResult() {
        return $this->result;
    }

    public function permute($source, $permutated=array()) {
        if (empty($permutated)){
            $this->result = array();
        }
        if (empty($source)){
            $this->result[] = $permutated;
        } else {
            for($i=0; $i<count($source); $i++){
                $new_permutated = $permutated;
                $new_permutated[] = $source[$i];
                $new_source =    array_merge(array_slice($source,0,$i),array_slice($source,$i+1));
                $this->permute($new_source, $new_permutated);
            }
        }
        return $this;
    }
}

$arr = array(1,2,3,4,5);
$p = new Permutation();
print_r($p->permute($arr)->getResult());

Las últimas tres líneas para probar mi clase.

Answer 7

Esta es una función recursiva simple que imprime todas las permutaciones (escritas en pseudocódigo)

function rec(n, k) {
    if (k == n) {
        for i = 0 to n-1
            print(perm[i], '' '');
        print(''/n'');
    }
    else {
        for i = 0 to n-1 {
            if (not used[i]) {
                used[i] = true;
                perm[k] = i;
                rec(n, k+1);
                used[i] = false;
            }
        }
    }
}

Y se llama así:

rec(9, 0);

Answer 8

He portado el código de itertools de Python enumerado here (usando generadores). La ventaja sobre las soluciones publicadas hasta ahora es que le permite especificar r (tamaño de permutación).

function permutations($pool, $r = null) {
    $n = count($pool);

    if ($r == null) {
        $r = $n;
    }

    if ($r > $n) {
        return;
    }

    $indices = range(0, $n - 1);
    $cycles = range($n, $n - $r + 1, -1); // count down

    yield array_slice($pool, 0, $r);

    if ($n <= 0) {
        return;
    }

    while (true) {
        $exit_early = false;
        for ($i = $r;$i--;$i >= 0) {
            $cycles[$i]-= 1;
            if ($cycles[$i] == 0) {
                // Push whatever is at index $i to the end, move everything back
                if ($i < count($indices)) {
                    $removed = array_splice($indices, $i, 1);
                    array_push($indices, $removed[0]);
                }
                $cycles[$i] = $n - $i;
            } else {
                $j = $cycles[$i];
                // Swap indices $i & -$j.
                $i_val = $indices[$i];
                $neg_j_val = $indices[count($indices) - $j];
                $indices[$i] = $neg_j_val;
                $indices[count($indices) - $j] = $i_val;
                $result = [];
                $counter = 0;
                foreach ($indices as $indx) {
                    array_push($result, $pool[$indx]);
                    $counter++;
                    if ($counter == $r) break;
                }
                yield $result;
                $exit_early = true;
                break;
            }
        }
        if (!$exit_early) {
            break; // Outer while loop
        }
    }
}

¡Funciona para mí, pero no hay promesas! Ejemplo de uso:

$result = iterator_to_array(permutations([1, 2, 3, 4], 3));
foreach ($result as $row) {
    print implode(", ", $row) . "/n";
}

Answer 9

Orden lexicográfico No hay recursión. Casi sin límites para la longitud de la matriz. No hay ningún tipo. Se está ejecutando bastante rápido. Es fácil de entender Menos: da un aviso, pero puede agregar una condición para comenzar a comparar con el segundo elemento o error_reporting (0).

$a = array(
1,
2,
3,
4,
5
 );
    $b = array_reverse($a);
    print_r($a);
   //here need "br"
  while ($a != $b)
{
foreach(array_reverse($a, true) as $k => $v)
    {
    if ($v < $a[$k + 1])
        {
        foreach(array_reverse($a, true) as $ka => $val)
            {
            if ($val > $v) break;
            }

        $ch = $a[$k];
        $a[$k] = $a[$ka];
        $a[$ka] = $ch;
        $c = array_slice($a, 0, $k + 1);
        print_r($a = array_merge($c, array_reverse(array_slice($a, $k + 1))));
        //here need "br"
        break;
        }
       }
      }

Answer 10

Prueba esto...

//function to generate and print all N! permutations of $str. (N = strlen($str))

function permute($str,$i,$n) {
   if ($i == $n)
       print "$str/n";
   else {
        for ($j = $i; $j < $n; $j++) {
          swap($str,$i,$j);
          permute($str, $i+1, $n);
          swap($str,$i,$j); // backtrack.
       }
   }
}

// function to swap the char at pos $i and $j of $str.

function swap(&$str,$i,$j) {
    $temp = $str[$i];
    $str[$i] = $str[$j];
    $str[$j] = $temp;
}   
$str = "0123";
permute($str,0,strlen($str)); // call the function.

Answer 11

Tengo algo que te puede gustar

function combination_number($k,$n){
    $n = intval($n);
    $k = intval($k);
    if ($k > $n){
        return 0;
    } elseif ($n == $k) {
        return 1;
    } else {
        if ($k >= $n - $k){
            $l = $k+1;
            for ($i = $l+1 ; $i <= $n ; $i++)
                $l *= $i;
            $m = 1;
            for ($i = 2 ; $i <= $n-$k ; $i++)
                $m *= $i;
        } else {
            $l = ($n-$k) + 1;
            for ($i = $l+1 ; $i <= $n ; $i++)
                $l *= $i;
            $m = 1;
            for ($i = 2 ; $i <= $k ; $i++)
                $m *= $i;            
        }
    }
    return $l/$m;
}

function array_combination($le, $set){

    $lk = combination_number($le, count($set));
    $ret = array_fill(0, $lk, array_fill(0, $le, '''') );

    $temp = array();
    for ($i = 0 ; $i < $le ; $i++)
        $temp[$i] = $i;

    $ret[0] = $temp;

    for ($i = 1 ; $i < $lk ; $i++){
        if ($temp[$le-1] != count($set)-1){
            $temp[$le-1]++;
        } else {
            $od = -1;
            for ($j = $le-2 ; $j >= 0 ; $j--)
                if ($temp[$j]+1 != $temp[$j+1]){
                    $od = $j;
                    break;
                }
            if ($od == -1)
                break;
            $temp[$od]++;
            for ($j = $od+1 ; $j < $le ; $j++)    
                $temp[$j] = $temp[$od]+$j-$od;
        }
        $ret[$i] = $temp;
    }
    for ($i = 0 ; $i < $lk ; $i++)
        for ($j = 0 ; $j < $le ; $j++)
            $ret[$i][$j] = $set[$ret[$i][$j]];   

    return $ret;
}

Aquí es cómo usarlo:

Para obtener el número de combinaciones:

combination_number(3,10); // returns number of combinations of ten-elements set.

Para obtener todas las combinaciones posibles:

$mySet = array("A","B","C","D","E","F");
array_combination(3, $mySet); // returns all possible combinations of 3 elements of six-elements set.

Espero que hagas uso de eso.