Genere el conjunto de permutaciones prepend-append en orden lexicográficamente ordenado

Joe Z. 03/06/2015. 10 answers, 658 views
code-golf combinatorics

Defina una prepend-append sequence de longitud n para que sea una permutación de los números 1, 2, ..., n que pueden generarse mediante el siguiente procedimiento:

  • Comience con el número 1 .

  • Para cada número de 2 a n , coloque este número al comienzo o al final de la secuencia (ya sea antes o append , de ahí el nombre de la secuencia).

Por ejemplo, esta es una forma válida de generar una secuencia prepend-append de longitud 4:

1
21     [beginning]
213    [end]
2134   [end] 

Su tarea es construir un programa o función que tomará un número n del 3 al 30 como entrada, e imprimirá o devolverá todas las secuencias de antependencia de longitud n en orden lexicográfico (si está produciendo cadenas y no listas, números anteriores) 9 se representará como letras a-u , para preservar la longitud de la cuerda). Por ejemplo, este es ese orden para n = 4 :

1234  [RRR]
2134  [LRR]
3124  [RLR]
3214  [LLR]
4123  [RRL]
4213  [LRL]
4312  [RLL]
4321  [LLL] 

En general, hay 2 permutaciones prepend-append n-1 de longitud n .

No puede usar ninguna función integrada de clasificación en su idioma en su código. El programa más corto para hacer esto en cualquier idioma gana.

5 Comments
xnor 03/06/2015
No soy partidario del requisito de formato de salida, en particular, la conversión a letras a-u . ¿Podemos simplemente sacar listas de números?
3 Optimizer 03/06/2015
Es posible que desee aceptar la respuesta después de un tiempo ya que algunas personas tienden a no responder una pregunta si tiene una respuesta aceptada.
1 Optimizer 03/06/2015
Entonces, tienes una respuesta incorrecta aceptada.
2 Joe Z. 03/06/2015
FryAmTheEggman publicó su respuesta 21 minutos antes de que editases la tuya.
2 Joe Z. 03/06/2015
@Optimizer No creo que sea la manera más extraña: la respuesta de FryAmTheEggman fue de 19 bytes de longitud 21 minutos antes que la tuya. Eso lo convierte en la respuesta más breve publicada más temprano.

10 Answers


Optimizer 03/06/2015.

CJam, 22 20 19 17 bytes

]]l~{)f+_1fm>|}/p 

Code expansion :

]]                   "Put [[]] onto stack. What we will do with this array of array is";
                     "that in each iteration below, we will first append the next";
                     "number to all present arrays, then copy all the arrays and";
                     "move the last element to first in the copy";
  l~                 "Read input number. Lets call it N";
    {         }/     "Run this code block N times ranging from 0 to N - 1";
     )f+             "Since the number on stack starts from 0, add 1 to it and append";
                     "it to all arrays in the array of array beginning with [[]]";
        _1fm>        "Copy the array of array and move last element from all arrays";
                     "to their beginning";
             |       "Take set union of the two arrays, thus joining them and eliminating";
                     "duplicates. Since we started with and empty array and started adding";
                     "numbers from 1 instead of 2, [1] would have appeared twice if we had";
                     "simply done a concat";
                p    "Print the array of arrays"; 

How it works :

Esta es una versión de depuración del código:

]]l~ed{)edf+ed_ed1fm>ed|ed}/edp 

Veamos cómo funciona para la entrada 3 :

[[[]] 3]                                 "]]l~"            "Empty array of array and input";
[[[]] 1]                                 "{)"              "First iteration, increment 0";
[[[1]]]                                  "{)f+"            "Append it to all sub arrays";
[[[1]] [[1]]]                            "{)f+_"           "Copy the final array of array";
[[[1]] [[1]]]                            "{)f+_1fm>"       "shift last element of each";
                                                           "sub array to the beginning";
[[[1]]]                                  "{)f+_1fm>|}"     "Take set based union";
[[[1]] 2]                                "{)"              "2nd iteration. Repeat";
[[[1 2]]]                                "{)f+"
[[[1 2]] [[1 2]]]                        "{)f+_";
[[[1 2]] [[2 1]]]                        "{)f+_1fm>";
[[[1 2] [2 1]]]                          "{)f+_1fm>|}";
[[[1 2] [2 1]] 3]                        "{)";
[[[1 2 3] [2 1 3]]]                      "{)f+"
[[[1 2 3] [2 1 3]] [[1 2 3] [2 1 3]]]    "{)f+_";
[[[1 2 3] [2 1 3]] [[3 1 2] [3 2 1]]]    "{)f+_1fm>";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm>|}";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm>|}/"; 

Pruébalo en línea aquí


alephalpha 03/06/2015.

Haskell, 47 bytes

f 1=[[1]]
f n=(\x->map(++[n])x++map(n:)x)$f$n-1 
3 comments
1 nimi 03/06/2015
Pasar a la comprensión de la lista ahorra algunos bytes: f n=[[n:x,x++[n]]|x<-f$n-1]>>=id (usando la función concat código-golfistas >>=id ).
1 proud haskeller 03/07/2015
@nimi pero está en el orden incorrecto r
nimi 03/08/2015
@proudhaskeller: Oh querido, no leí las especificaciones con cuidado. Traté de solucionarlo y encontré cuatro formas ligeramente diferentes, todas de la misma longitud que la versión de @ alephalpha, por lo que no puedo ofrecer una mejora. f n=[x++[n]|x<-f$n-1]++[n:x|x<-f$n-1] , f n=map(++[n])(f$n-1)++[n:x|x<-f$n-1] , f n=map(++[n])(f$n-1)++map(n:)(f$n-1) , f n=(++[n])#n++(n:)#n;p#i=map p$f$i-1

xnor 03/06/2015.

Python 2, 68

 f=lambda n:[[1]]*(n<2)or[x*b+[n]+x*-b for b in[1,-1]for x in f(n-1)] 

Muestra una lista de listas de números.

Una solución recursiva. Para n==1 , salida [[1]] . De lo contrario, agregue n al inicio o al final de todas (n-1) -permutaciones. El preanálisis hace que la permutación sea lexicográficamente posterior a la adición, por lo que las permutaciones permanecen ordenadas.

El "booleano" b codifica si poner [n] al principio o al final. En realidad, movemos el resto de la lista x en la expresión x*b+[n]+x*-b . Poner b como -1 o 1 permite cambiar de sentido al negar, ya que una lista multiplicada por -1 es la lista vacía.


FryAmTheEggman 03/06/2015.

Pyth, 19

usCm,+dH+HdGr2hQ]]1 

Pruébalo en línea aquí

Este es un programa completo que toma datos de stdin.

Esto funciona de manera similar a la solución de xnor, pero genera los valores un poco fuera de servicio, por lo que deben reordenarse. Lo que sucede en cada nivel es que cada lista anterior de valores tiene el nuevo valor agregado al final y al principio, y cada uno de ellos está envuelto en una tupla de 2 que se envuelve en una lista. Por ejemplo, el primer paso hace esto:

[[1]]
[([1,2], [2,1])] 

Luego, esta lista de tuplas se comprime (y luego se suma para eliminar la lista más externa). En el primer caso, esto simplemente da el valor desenvuelto desde arriba, ya que solo hay un valor en la lista.

Pasos que muestran 2-> 3:

([1,2], [2,1])
[([1,2,3],[3,1,2]),([2,1,3],[3,2,1])]
([1,2,3],[2,1,3],[3,1,2],[3,2,1]) 

alephalpha 03/06/2015.

Mathematica, 57 54 49 bytes

f@1=NO 

Ejemplo:

f[4] 

{{1, 2, 3, 4}, {2, 1, 3, 4}, {3, 1, 2, 4}, {3, 2, 1, 4}, {4, 1, 2, 3} , {4, 2, 1, 3}, {4, 3, 1, 2}, {4, 3, 2, 1}}


randomra 04/13/2017.

J, 26 bytes

0|:<:((,,.,~)1+#)@[&0,.@1:

   (0|:<:((,,.,~)1+#)@[&0,.@1:) 3
1 2 3
2 1 3
3 1 2
3 2 1 

Mejora de 1 byte gracias a FUZxxl .

1 comments
FUZxxl 03/06/2015
Sustituto,. para ,"1 por un personaje".

Pietu1998 04/13/2017.

Pyth, 343331 29

Básicamente una traducción de la respuesta de Python de xnor . Todavía no soy bueno con Pyth, por lo que las sugerencias de mejora son bienvenidas.

Define una función y para devolver una lista de listas de enteros.

L?]]1 

Update: 2 bytes guardados gracias a FryAmTheEggman .

Explicación:

L                                  define a function y with argument b that returns
 ?*]]1 
4 comments
FryAmTheEggman 03/06/2015
Algunas cosas pyth: -b1 puede ser tb , [1_1) puede ser ,1_1 (sin embargo, puede soltar el corchete de cierre ya que solo necesita contar los bytes necesarios para realizar la función, aunque no podrá llamar sin cerrarlo), y no necesita incluir b en una lista ya que pyth convierte automáticamente a la lista al agregar una lista a un int.
FryAmTheEggman 03/06/2015
Se me ocurrió una forma de salvar varios bytes haciendo manualmente el segundo mapa sobre [1,-1] . Puedo guardar bytes para codificar algo tan corto, especialmente cuando simplificas la lógica. Me sale L?]]1
Pietu1998 03/06/2015
@FryAmTheEggman En realidad, puede querer agregar eso como su propia respuesta. Eso es simplemente increíble.
FryAmTheEggman 03/06/2015
OK, quería intentar vencer a CJam antes de publicar, pero creo que el truco zip es lo suficientemente interesante como para merecer su publicación. Buena suerte con Pyth;)

edc65 03/07/2015.

JavaScript (ES6) 73 80

Implementación de JavaScript de la buena solución de @ Optimizer.

Recursivo (73):

 R=(n,i=1,r=[[1]])=>++i>n?r:r.map(e=>r.push([i,...e])+e.push(i))&&R(n,i,r) 

Iterativo (74):

 F=n=>(i=>NO 

Test en la consola de Firefox / FireBug

 R(4) 

[[1, 2, 3, 4], [2, 1, 3, 4], [3, 1, 2, 4], [3, 2, 1, 4], [4, 1, 2, 3] , [4, 2, 1, 3], [4, 3, 1, 2], [4, 3, 2, 1]]


Digital Trauma 03/06/2015.

Pure Bash, 103

Más de lo que esperaba:

a=1..1
for i in {2..9} {a..u};{
((++c<$1))||break
a={${a// /,}}
a=`eval echo $a$i $i$a`
}
echo ${a%%.*} 

Brett Ryan 03/08/2015.

Mi solución Java:

public static void main(String[] args) {
    listPrependAppend(4);
}

private static void listPrependAppend(int n) {
    int total = (int) Math.pow(2, n - 1);
    int ps;
    boolean append;
    String sequence;
    String pattern;

    for (int num = 0; num < total; num++) {
        sequence = "";
        pattern = "";
        append = false;
        ps = num;
        for (int pos = 1; pos < n + 1; pos++) {
            sequence = append ? (pos + sequence) : (sequence + pos);
            append = (ps & 0x01) == 0x01;
            ps = ps >> 1;
            if (pos < n) {
                pattern += append ? "L" : "R";
            }
        }
        System.out.format("%s\t[%s]%n", sequence, pattern);
    }
} 
4 comments
Brett Ryan 03/08/2015
Oh fark, ahora después de ver las otras respuestas, veo lo que quieres decir con la respuesta más breve.
2 Joe Z. 03/08/2015
Si bien su solución es respetable, conciso y bien presentado por derecho propio, tiene razón en que no es un buen candidato para el problema en cuestión.
1 ProgramFOX 03/08/2015
@BrettRyan Puede hacer que su código sea mucho más corto eliminando espacios en blanco innecesarios y usando nombres de variables de un char. También puede reemplazar false por algo como 5<4 .
1 Brett Ryan 03/08/2015
Gracias chicos. Fue mi primer intento de participar en desafíos de código. Solo estaba buscando algunos desafíos de programación y no me di cuenta de que el objetivo era obtener la solución más corta. :) Gracias por dejarme participar.

Related questions

Hot questions

Language

Popular Tags