Encontrar todas las permutaciones en orden creciente

Question

Dado un conjunto de números distintos, digamos, {1, 2, 3, 4, 5, 6}, encuentra todas las permutaciones que contengan 3 números. Todas las permutaciones tienen que estar en orden ascendente.

Por ejemplo, algunas permutaciones correctas serían {1, 2, 3}, {2, 4, 6}, etc. {2, 3, 1} sería incorrecta porque no está en orden ascendente.

¿Cómo se resuelven este tipo de cuestiones? Digamos que, en lugar de elegir 3 números, tuviéramos que elegir 4 o 5, o que el conjunto dado fuera diferente, ¿cuál sería el planteamiento general?

Gracias.

P.D.: No sólo tienes que decir el número de permutaciones posibles, sino también enumerarlas.

Answer 1

Como todos los números del conjunto son distintos, las permutaciones que contienen 3 números en orden ascendente son: $$^6C_3$$ La razón es que cualquier selección de 3 números del conjunto puede ordenarse de forma ascendente de una sola manera.
Por lo tanto, las permutaciones que contienen 4 números en orden ascendente son: $$^6C_4$$ También las permutaciones que contienen 5 números en orden ascendente son: $$^6C_5$$

Answer 2

Para imprimir una lista de todas las permutaciones crecientes formadas por tres elementos del conjunto $\{1,2,3,\ldots,n\},$ utilizar un bucle anidado:

for i = 1 to n-2 {
  for j = i+1 to n-1 {
    for k = j+1 to n {
      print {i,j,k}
    }
  }
}

Para $k$ elementos, podría mantener la permutación en una matriz $p$ de longitud $k:$

for i = 1 to k {p[i] = i};   /* initialize p to {1,2,...,k} */
repeat {
  print p;
  i = k;
  /* find the rightmost incrementable element.  p[i] can't exceed n+i-k. */
  while i > 0 and p[i] == n+i-k {
    i = i - 1
  };
  if i > 0 {    /* if there exists an incrementable element... */
    p[i] = p[i] + 1;     /* increment it */
    for j = i + 1 to k {    /* and set all subsequent elts to their min values */
      p[j] = p[j-1] + 1
    } 
  }
} until i == 0

Si el conjunto está formado por elementos distintos de $1,\ 2,\ \ldots, n,$ y luego ordenar los elementos: $a_1< a_2<\ldots< a_n.$ Utilice el algoritmo anterior, pero en lugar de imprimir $p,$ imprimir los elementos indexados por $p,$ es decir $a_{p_1},\ a_{p_2},\ \ldots, a_{p_k}.$

Multisets: Si los elementos no son distintos, es decir, si se nos da un multiconjunto en lugar de un conjunto, el algoritmo anterior no puede utilizarse tal cual, ya que producirá duplicados. Supongamos de nuevo que hemos ordenado los elementos: $a_1\le a_2\le\ldots\le a_n.$

Dado el multiconjunto $\{3,5,5,5,6,6\},$ por ejemplo, tenemos $a_1=3,$ $a_2=a_3=a_4=5,$ $a_5=a_6=6.$ Por ejemplo, no querríamos imprimir ambos $a_1a_2a_3a_5$ y $a_1a_2a_4a_6,$ ya que son la misma cosa: $3556.$ La solución para esto es exigir que si incluimos dos de $a_2,\ a_3,\ a_4,$ incluimos los dos de menor índice, a saber $a_2$ y $a_3,$ en lugar de $a_2$ y $a_4$ o $a_3$ y $a_4.$ Asimismo, si incluimos uno de $a_5,\ a_6,$ incluimos el de menor índice: $a_5$ en lugar de $a_6.$

Para ello, modificamos el algoritmo anterior definiendo un incremento mínimo para cada una de las $n$ elementos ordenados del multiconjunto: $r_1=1,$ $r_2=3,$ $r_3=2,$ $r_4=1,$ $r_5=2,$ $r_6=1.$ El algoritmo modificado es el siguiente:

/* assume the elements a[1], a[2], ..., a[n] to be sorted in ascending order */
/* compute least increments */
r[n] = 1;
for i = n-1 downto 1 {
  if a[i] == a[i+1] {r[i] = r[i+1] + 1} else {r[i] = 1}
};
/* initialize p to {1,2,...,k} */
for i = 1 to k {p[i] = i};
repeat {
  for j = 1 to k {print a[p[j]]};
  print <newline>;
  i = k;
  /* find the rightmost incrementable element.  p[i] can't exceed n+i-k. */
  while i > 0 and p[i]+r[p[i]] > n+i-k {
    i = i - 1
  };
  if i > 0 {    /* if there exists an incrementable element... */
    p[i] = p[i] + r[p[i]];     /* increment it */
    for j = i + 1 to k {    /* and set all subsequent elts to their min values */
      p[j] = p[j-1] + 1
    } 
  }
} until i == 0

Answer 3

El siguiente algoritmo está tomado directamente de la obra de Donald Knuth El arte de la programación informática: Pre-Fascículo 2B: Un borrador de 7.2.1.2: Generar todas las permutaciones . Usted dice que quiere que sus elementos sean permutados y listados en orden creciente; la descripción más general del orden creciente se llama orden lexicográfico . Aquí está Knuth Algoritmo L que genera las permutaciones deseadas en orden lexicográfico:

Algoritmo L (Generación de permutaciones lexicográficas). Dada una secuencia de $n$ elementos $a_1a_2\dots a_n$ , ordenados inicialmente de forma que $a_1 \leq a_2 \leq \cdots \leq a_n$ este algoritmo genera todas las permutaciones de { $a_1,a_2,\dots, a_n$ }, visitándolos en orden lexicográfico.

Por ejemplo, las permutaciones de {1,2,2,3} son

1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321, 3122, 3212, 3221,

ordenados lexicográficamente. Un elemento auxiliar $a_0$ se supone que está presente por conveniencia; $a_0$ debe ser estrictamente menor que el elemento más grande $a_n$ .

L1. Visita la permutación $a_1a_2\dots a_n$ .

L2. [Buscar $j$ .] Establecer $j \leftarrow n - 1$ . Si $a_j \geq a_{j+1}$ , disminución $j$ por 1 repetidamente hasta que $a_j < a_{j+1}$ . Terminar el algoritmo si $j=0$ . (En este punto $j$ es el menor subíndice tal que ya hemos visitado todas las permutaciones que empiezan por $a_1 \dots a_j$ . Por lo tanto, la siguiente permutación lexicográfica aumentará el valor de $a_j$ .)

L3. [Aumento $a_j$ .] Establecer $l \leftarrow n$ . Si $a_j \geq a_l$ , disminución $l$ por 1 repetidamente hasta que $a_j < a_l$ . Entonces intercambia $a_j \leftrightarrow a_l$ . (Desde $a_{j+1} \geq \cdots \geq a_n$ , elemento $a_l$ es el menor elemento mayor que $a_j$ que puede seguir legítimamente $a_1 \dots a_{j-1}$ en una permutación. Antes del intercambio teníamos $a_{j+1} \geq \cdots \geq a_{l-1} \geq a_l > a_j \geq a_{l+1} \geq \cdots \geq a_n$ después del intercambio, tenemos $a_{j+1} \geq \cdots \geq a_{l-1} \geq a_j > a_l \geq a_{l+1} \geq \cdots \geq a_n$ .)

L4. [Invertir $a_{j+1} \cdots a_n$ .] Establecer $k \leftarrow j + 1$ y $l \leftarrow n$ . Entonces, si $k<l$ Intercambio $a_k \leftrightarrow a_l$ , set $k \leftarrow k+1$ , $l \leftarrow l-1$ y repetir hasta que $k \geq l$ . Volver a L1 .

Answer 4

En mi opinión, no está pidiendo permutaciones sino combinaciones . Si estoy en lo cierto, entonces la respuesta dada sobre la Algoritmo L no cubre su problema.

Suponiendo que usted pida efectivamente combinaciones: hay 20 y aquí vienen.

 1  1 2 3
 2  1 2 4
 3  1 2 5
 4  1 2 6
 5  1 3 4
 6  1 3 5
 7  1 3 6
 8  1 4 5
 9  1 4 6
10  1 5 6
11  2 3 4
12  2 3 5
13  2 3 6
14  2 4 5
15  2 4 6
16  2 5 6
17  3 4 5
18  3 4 6
19  3 5 6
20  4 5 6
Tengo un software para hacer lo mismo en casos más generales. La esencia de la codificación es un bucle anidado, como sigue (en Pascal).

Program loops;
var
  tel, k1, k2, k3 : integer;
begin
  tel := 0;
  for k1 := 1 to 6 do
  begin
    for k2 := k1+1 to 6 do
    begin
      for k3 := k2+1 to 6 do
      begin
        tel := tel + 1;
        Writeln(tel:2,'  ',k1,' ',k2,' ',k3);
      end;
    end;
  end;
end.
El siguiente es el programa más general (recursivo) mencionado, con la misma salida, sin embargo.

Program recursie;  
procedure combi(n,k : integer);
{
  Combinations k out of n
}
var
  t : integer;
  loper : array of integer;  
  procedure loops(var tel : integer; diep : integer);
  {
    Recursive nested loops
  }
  var
    d : integer;  
    procedure PRINT;
    var
      i : integer;
    begin
      Write(tel+1:3,'  ');
      for i := 1 to k do
        Write(loper\[i\],' ');
      Writeln;
    end;  
  begin
    if diep = k then
    begin
      PRINT;
      tel := tel + 1;
    end else begin
      for d := loper\[diep\]+1 to n do
      begin
        loper\[diep+1\] := d;
        loops(tel,diep+1);
      end;
    end;
  end;  
begin
  t := 0;
  SetLength(loper,k+1);
  loper\[0\] := 0;
  loops(t,0);
end;
{
procedure test;
var
  k : integer;
begin
  for k := 0 to 6 do
  begin
    combi(6,k);
    Writeln;
  end;
end;
}
begin
  combi(6,3);
end.

Answer 5

El mismo algoritmo (creo) en forma más folclórica, para encontrar la siguiente (en sentido lexicográfico) permutación :

Considere la posibilidad de encontrar el siguiente permutación de los números $(1,2,3,4,5,6,7,8)$ , a continuación, como ejemplo, $(2,6,8,7,4,5,3,1)$

Encuentre el más a la derecha par de números adyacentes en el actual permutación que están en orden lexicográfico. Si no existe tal par, ya está en la última permutación. En este caso, ese par es $(4,5)$

EDITAR:

Llame al primer número $A$

Empezando por el segundo número de la pareja, encuentra el número más a la derecha que sea mayor que $A$ ; podría ser el segundo número del par, como en este ejemplo. Llama a este número $B$ .

Intercambiar A y B. En este caso, ahora tenemos $(2,6,8,7,5,4,3,1)$

Por último, toma los números que siguen a B y colócalos en orden lexicográfico. En este caso, tomamos $(...4,3,1)$ , reordenar para obtener $(...1,3,4)$ y tener como siguiente permutación $(2,6,8,7,5,1,3,4)$