Hinweis: Dies ist ein Versuch, die Permutationsfrage (n) von guest271314 zu recyceln.

Es gibt ein interessantes Muster, das sich bildet, wenn Sie die Unterschiede zwischen lexografisch sortierten Permutationen von Basis-10-Zahlen mit aufsteigenden eindeutigen Ziffern finden. Hat zum Beispiel 123Permutationen:

123 132 213 231 312 321

Wenn Sie die Unterschiede zwischen diesen finden, erhalten Sie die Reihenfolge

9 81 18 81 9

Die alle durch neun teilbar sind (aufgrund der Ziffernsumme der Basis-10-Zahlen) und palindromisch sind.

Insbesondere wenn wir die nächste Nummer verwenden 1234, erhalten wir die Sequenz

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

Dies erweitert die vorherige Sequenz und bleibt gleichzeitig um palindrom . Dieses Muster gilt immer, auch wenn Sie mehr als Zahlen verwenden, obwohl die Länge der Sequenz für Zahlen beträgt . Beachten Sie, dass wir zur Verwendung der obigen Zahlen nicht zu einer anderen Basis wechseln, sondern nur die Zahl mit multiplizieren , z. B. .$693$n ! - 1 n 10 x [ 1 , 12 , 11 ] 10 = 1 ≤ 10 2 + 12 ≤ 10 1 + 11 ≤ 10 0 = 23110$n!-1$$n$0 to 9$10^x$$[1,12,11]_{10} = 1*10^2 + 12*10^1 + 11*10^0 = 231$

Ihr Ziel ist es, diese Sequenz zu implementieren, indem Sie jedes Element als Vielfaches von neun zurückgeben. Zum Beispiel sind die ersten 23 Elemente dieser Sequenz:

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

Einige andere Testfälle (0 indiziert):

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

Regeln:

• Die Einreichung kann eine der folgenden sein:
  • Ein Programm / eine Funktion, die eine Nummer annimmt und die Nummer an diesem Index zurückgibt, entweder 0 oder 1 indiziert.
  • Ein Programm / eine Funktion, die eine Zahl annimmt und bis zum ten Index zurückkehrt, entweder 0 oder 1 indiziert.$n$$n$
  • Ein Programm / eine Funktion, die die Sequenz unendlich ausgibt / zurückgibt.
• Das Programm sollte theoretisch in der Lage sein, theoretisch bis zum Element und darüber hinaus zu arbeiten, obwohl ich verstehe, ob Zeit- / Speicherbeschränkungen dies fehlschlagen lassen. Dies bedeutet insbesondere, dass Sie die Ziffern nicht verketten und als Basis 10 auswerten können, da so etwas wie falsch wäre.$11!-1$$012345678910$
• Dies ist Code-Golf , also gewinnt die kürzeste Implementierung für jede Sprache!

Anmerkungen:

• Dies ist OEIS A217626
• Ich biete eine Prämie von 500 für eine Lösung an, die die Elemente direkt berechnet, ohne die tatsächlichen Permutationen zu berechnen.
• Die Sequenz funktioniert für alle zusammenhängenden Ziffern. Zum Beispiel sind die Unterschiede zwischen den Permutationen von dieselben wie für .$[1,2,3,4]_{10}$$[-4,-3,-2,-1]_{10}$

Gelee , 9 Bytes

,‘œ?ŻḌI÷9

Probieren Sie es online aus! (drucke das n-te Element aus)

Probieren Sie es online aus! (20 erste Elemente)

Erläuterung:

      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 hat das eingebaute Element, œ?das die dritte nPermutation einer Liste in ungefähr linearer Zeit berechnet. Sehr nützlich.)

Holzkohle , 71 Bytes

≔⟦Ｎ⊕θ⟧ηＷ⌈η≧÷Ｌ⊞ＯυＥη﹪κ⊕Ｌυη≔⁰δＦ²«≔Ｅυλζ≔⟦⟧ηＦ⮌Ｅυ§κι«⊞η§ζκ≔Φζ⁻μκζ»≦⁻↨ηχδ»Ｉ÷δ⁹

Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Erläuterung:

≔⟦Ｎ⊕θ⟧η

Holen Sie sich eine Liste mit der Eingabe und einer mehr als der Eingabe.

Ｗ⌈η

Wiederholen, bis beide Werte Null sind.

≧÷Ｌ⊞ＯυＥη﹪κ⊕Ｌυη

Führen Sie für beide Werte eine faktorielle Basisumrechnung durch. Dies ist das erste Mal, dass ich tatsächlich ≧auf einer Liste verwendet habe!

≔⁰δ

Löschen Sie das Ergebnis.

Ｆ²«

Schleife über jede faktorielle Basisnummer.

≔Ｅυλζ

Machen Sie eine Liste der Ziffern von 0 bis Länge - 1.

≔⟦⟧η

Initialisieren Sie das Ergebnis in eine leere Liste.

Ｆ⮌Ｅυ§κι«

Schleife über die Ziffern der faktoriellen Basisnummer.

⊞η§ζκ

Fügen Sie dem Ergebnis die nächste Permutationsziffer hinzu.

≔Φζ⁻μκζ»

Entfernen Sie diese Ziffer aus der Liste.

≦⁻↨ηχδ»

Konvertieren Sie die Permutation als Basis-10-Zahl und subtrahieren Sie das bisherige Ergebnis davon.

Ｉ÷δ⁹

Teilen Sie das Endergebnis durch 9 und werfen Sie es in eine Zeichenfolge.

Perl 6 , 82 Bytes

-2 Bytes dank Jo King

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

Probieren Sie es online aus!

0-indiziert. Zählt nicht alle Permutationen auf. Sollte theoretisch für alle n funktionieren, wird aber für n> 65536 mit "Zu viele Argumente im Reduzierungsarray" gerettet.

Die folgende 80-Byte- Version funktioniert für n bis zu 98! -2 und ist viel schneller:

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

Probieren Sie es online aus!

Die folgende 53-Byte- Version sollte theoretisch für alle n funktionieren, jedoch für n> = 20 mit "Weigerung, mehr als 20 Elemente zu permutieren".

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

Probieren Sie es online aus!

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])

Probieren Sie es online aus!

1-indiziert.

@ guest271314 Die Meinung ist richtig. Die direkte Permutationsberechnung ist kürzer ...

Erläuterung

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
)

Ursprüngliche Lösung (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

Probieren Sie es online aus!

Link ist zu einer längeren Version für Leistung gemacht. Array(n+1)wird Array(Math.min(n+1,15)), um Demo zum Laufen zu bringen. Funktioniert theoretisch bis unendlich (bis zur Stapelgrenze in der Praxis).

Erläuterung

Ich meine, es gibt zu viel zu erklären.

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

Pyth, 15 14 Bytes

.+m/i.PdSQT9,h

Gibt den n-ten Term zurück. Probieren Sie es hier aus .

.+                     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

J , 44 , 41 Bytes

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

Probieren Sie es online aus!

Hinweis: funktioniert auch für 10! Testfall, verliert dort aber etwas an Präzision ...

ursprüngliche Erklärung

(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

JavaScript (ES6), 112 Byte

Sehr ähnlich dem Algorithmus von Shieru Asakoto .

n=>(g=N=>(h=a=>k>n?(F=r=>--i?F(+a.splice(N/(k/=i),1)+r*10,N%=k):r/9)``:h([i+1,...a],k*=i++))([i=k=1]))(n++)-g(n)

Probieren Sie es online aus!