9erutaciones férreas

8

Nota: Este es un intento de reciclar las preguntas de permutación de guest271314

Hay un patrón interesante que se forma cuando encuentras las diferencias entre permutaciones ordenadas lexográficamente de números de base 10 con dígitos únicos ascendentes. Por ejemplo, 123tiene permutaciones:

123 132 213 231 312 321

Cuando encuentras las diferencias entre estos, obtienes la secuencia

9 81 18 81 9

Todos los cuales son divisibles por nueve (debido a la suma de dígitos de los números de base 10), además de ser palindrómicos.

Notablemente, si usamos el siguiente número arriba 1234, obtenemos la secuencia

9 81 18 81 9 702 9 171 27 72 18 693 18 72 27 171 9 702 9 81 18 81 9

69310n!1n0 to 910x[1,12,11]10=1102+12101+11100=231

Su objetivo es implementar esta secuencia, devolviendo cada elemento como un múltiplo de nueve. Por ejemplo, los primeros 23 elementos de esta secuencia son:

1 9 2 9 1 78 1 19 3 8 2 77 2 8 3 19 1 78 1 9 2 9 1

Algunos otros casos de prueba (0 indexados):

23     => 657
119    => 5336
719    => 41015
5039   => 286694
40319  => 1632373
362879 => 3978052
100    => 1
1000   => 4
10000  => 3
100000 => 3

Reglas:

  • La presentación puede ser cualquiera de:
    • Un programa / función que toma un número y devuelve el número en ese índice, ya sea 0 o 1 indexado.
    • nn
    • Un programa / función que genera / devuelve la secuencia infinitamente.
  • 11!1012345678910
  • Este es el , por lo que gana la implementación más corta para cada idioma.

Notas:

  • Esta es OEIS A217626
  • Estoy ofreciendo una recompensa de 500 por una solución que resuelve los elementos directamente sin calcular las permutaciones reales.
  • [1,2,3,4]10[4,3,2,1]10
Jo King
fuente
¿Cuál es el desempate para la recompensa?
nwellnhof el
2
No tiene mucho sentido "resolver los elementos directamente", ya que calcular la permutación en sí lleva tiempo lineal (en el tamaño de la entrada) (¿verdad?), Que ya es bastante bueno. ¿Solo quieres ver métodos geniales?
user202729
1
10!13628799 => -83676269
@ user202729 ¿Quizás el OP quiere algo de tiempo de registro o algoritmo de tiempo constante? Como se trata de una secuencia OEIS, dicho algoritmo puede ayudar a la investigación.
Shieru Asakoto
1
O(Γ1(n))

Respuestas:

5

Jalea , 9 bytes

,‘œ?ŻḌI÷9

Pruébalo en línea! (imprime el enésimo elemento)

Pruébalo en línea! (20 primeros elementos)

Explicación:

      I÷9      Compute the difference divided by 9 between
 ‘             the (n+1)th
  œ?           permutation
,              and
               the (n)th
  œ?           permutation
    Ż          of [0,1,2,...n]
     Ḍ         converted to decimal.

(Jelly tiene la función integrada œ?que calcula la npermutación de una lista en un tiempo aproximadamente lineal. Bastante útil).

usuario202729
fuente
4

Carbón , 71 bytes

≔⟦N⊕θ⟧ηW⌈η≧÷L⊞OυEη﹪κ⊕Lυη≔⁰δF²«≔Eυλζ≔⟦⟧ηF⮌Eυ§κι«⊞η§ζκ≔Φζ⁻μκζ»≦⁻↨ηχδ»I÷δ⁹

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

≔⟦N⊕θ⟧η

Obtenga una lista que contenga la entrada y una más que la entrada.

W⌈η

Repita hasta que ambos valores sean cero.

≧÷L⊞OυEη﹪κ⊕Lυη

Realice la conversión factorial de base en ambos valores. ¡Es la primera vez que lo uso en una lista!

≔⁰δ

Borrar el resultado.

F²«

Recorre cada número base factorial.

≔Eυλζ

Haga una lista de los dígitos de 0 a longitud - 1.

≔⟦⟧η

Inicialice el resultado en una lista vacía.

F⮌Eυ§κι«

Recorre los dígitos del número base factorial.

⊞η§ζκ

Agregue el siguiente dígito de permutación al resultado.

≔Φζ⁻μκζ»

Eliminar ese dígito de la lista.

≦⁻↨ηχδ»

Convierta la permutación como un número base 10 y reste el resultado hasta ahora.

I÷δ⁹

Divide el resultado final entre 9 y ponlo a cuerda.

Neil
fuente
3

Perl 6 , 82 bytes

-2 bytes gracias a Jo King

->\n{([-] map {$/=[^n];:10[map {|splice $/,$_,1},[R,] .polymod(1..n-2)]},n+1,n)/9}

Pruébalo en línea!

0 indexado. No enumera todas las permutaciones. Teóricamente debería funcionar para todos n, pero rescata para n> 65536 con "Demasiados argumentos en la matriz de aplanamiento".

La siguiente versión de 80 bytes funciona para n hasta 98! -2 y es mucho más rápida:

{([-] map {$/=[^99];:10[map {|splice $/,$_,1},[R,] .polymod(1..97)]},$_+1,$_)/9}

Pruébalo en línea!

La siguiente versión de 53 bytes debería funcionar teóricamente para todos n, pero rescata para n> = 20 con "negarse a permutar más de 20 elementos".

{[-](map {:10[$_]},permutations(1..$_+1)[$_,$_-1])/9}

Pruébalo en línea!

nwellnhof
fuente
2

JavaScript (Node.js) , 134 bytes

n=>(F=_=>f>n?((G=(n,z=0,x=f,y=l,b=[...a])=>y?G(n%(x/=y),+b.splice(n/x,1)+z*10,x,y-1,b):z)(n--)-G(n))/9:F(a.push(++l),f*=l))(a=[l=f=1])

Pruébalo en línea!

1 indexado.

La opinión de @ guest271314 es correcta. El cálculo de permutación directa es más corto ...

Explicación

n=>(                           // Function -
 F=_=>                         //  Helper func to calculate length needed
 f>n?                          //   If f > n (meaning the length is enough) -
  (
   (
    G=(                        //    Helper func to calculate permutation value -
     n,
     z=0,                      //     Initial values
     x=f,                      //     Made as copies because we need to alter
     y=l,                      //     these values and the function will be
     b=[...a]                  //     called twice
    )=>
    y?                         //     If still elements remaining -
     G(
      n%(x/=y),                //      Get next element
      +b.splice(n/x,1)+z*10,   //      And add to the temporary result
      x,
      y-1,                     //      Reduce length
      b                        //      Remaining elements
     )
    :z                         //     Otherwise return the permutation value
   )(n--)-G(n)                 //    Calculate G(n) - G(n - 1)
  )/9                          //    ... the whole divided by 9 
 :F(
  a.push(++l),                 //   Otherwise l = l + 1, push l into the array
  f*=l                         //   ... and calculate l!
 )
)(
 a=[l=f=1]                     //  Initial values
)

Solución original (159 bytes)

n=>(x=l=t=0n,P=(a,b=[])=>n?""+a?a.map(z=>P(a.filter(y=>y-z),[...b,z])):(v=b.reduce((u,y)=>u=u*10n+y),x?--n?0:t=v-x:0,x=v):0)([...Array(n+1))].map(_=>++l))&&t/9n

Pruébalo en línea!

El enlace es a una versión más larga hecha para el rendimiento. Array(n+1)se hace Array(Math.min(n+1,15))para que la demostración funcione. Teóricamente funciona hasta el infinito (hasta el límite de pila en la práctica).

Explicación

Quiero decir que hay mucho que explicar.

n=>(                             // Function
 x=l=t=0n,                       // Initialization
 P=(                             // Function to determine the permutation -
  a,                             //  remaining items
  b=[]                           //  storage
 )=>
 n?                              //  if we haven't reached the required permutation yet - 
  ""+a?                          //   if we haven't the last layer of loop - 
   a.map(                        //    loop over the entries -
    z=>      
    P(                           //     recurse -
     a.filter(y=>y-z),           //      pick out the selected number
     [...b,z]                    //      append to next 
    )
   )
  :(                             //   if we are at the last layer -
   v=b.reduce((u,y)=>u=u*10n+y), //    calculate the value of the permutation
   x?                            //    if not the first number -
    --n?                         //     if not the last -
     0                           //      do nothing
    :t=v-x                       //     else calculate difference
   :0,                           //    else do nothing
   x=v                           //    record ot anyway
  )
 :0                              //   else do nothing
)
(
 [...Array(n+1)].map(_=>++l)     // the list of numbers to permute
)&&t/9n                          // last difference divided by 9
Shieru Asakoto
fuente
FWIW, dado que esta implementación no devuelve todas las diferencias n, esta solución stackoverflow.com/a/34238979 proporciona un medio para obtener dos permutaciones adyacentes, o representaciones numéricas de permutaciones directamente por índice, que cuando se juega golf, debería reducir el código necesario para producir la salida (f(n) - f(n-1))/9para este tipo de respuesta seleccionado de acuerdo con la regla "Un programa / función que toma un número y devuelve el número en ese índice, ya sea 0 o 1 indexado". .
invitado271314
2

Pyth, 15 14 bytes

.+m/i.PdSQT9,h

Devuelve el enésimo término. Probarlo aquí .

.+                     Find the differences between adjacent elements of
   m                   mapping lambda d:
      .PdSQ                the dth permutation of input,
     i     T               converted to base 10
    /       9              divided by 9
             ,         over [Q+1,Q]
               h Q
               Q
lirtosiast
fuente
2

J , 44 , 41 bytes

(9%~[:(2-~/\])i.(10#.1+A.)[:i.@>.!inv)@>:

Pruébalo en línea!

Nota: ¡funciona incluso para 10! caso de prueba, pero pierde algo de precisión allí ...

explicación original

(9 %~ [: (2 -~&(10&#.)/\ ]) 1 + i. A. i.@>.@(!inv))@>:
(                                                 )@>: NB. add one to input
                                                       NB. since n-1 deltas
                                                       NB. gives n results
                                                       NB. call that "n"
(                               i.                )    NB. take the first n
(                                  A.             )    NB. lexicographically
                                                       NB. sorted items of
(                                     i.@         )    NB. 0 up to...
(                                        >.@      )    NB. the ceil of...
(                                           (!inv))    NB. the inverse of 
                                                       NB. the factorial
(                           1 +                   )    NB. add 1 so our
                                                       NB. lists start at 1
                                                       NB. instead of 0
(     [: (                )                       )    NB. apply what's in 
                                                       NB. parens to that
                                                       NB. list of lists
(        (2 -~        /\ ])                       )    NB. take successive
                                                       NB. differences BUT
(        (    &(10&#.)    )                       )    NB. convert each list
                                                       NB. to a base 10
                                                       NB. number first
(9 %~                                             )    NB. and divide every
                                                       NB. items of the
                                                       NB. result by 9
Jonás
fuente