9erilous 9ermutations

Question

Note: This is an attempt at recycling guest271314's permutation question(s)

There's an interesting pattern that forms when you find the differences between lexographically sorted permutations of base 10 numbers with ascending unique digits. For example, 123 has permutations:

123 132 213 231 312 321

When you find the differences between these, you get the sequence

9 81 18 81 9

Which are all divisible by nine (because of the digit sum of base 10 numbers), as well as being palindromic.

Notably, if we use the next number up, 1234, we get the sequence

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

Which extends the previous sequence while remaining palindromic around \$693\$. This pattern always holds, even when you start using more that 10 numbers, though the length of the sequence is \$n!-1\$ for \$n\$ numbers. Note that to use numbers above 0 to 9, we don't change to a different base, we just multiply the number by \$10^x\$, e.g. \$ [1,12,11]_{10} = 1*10^2 + 12*10^1 + 11*10^0 = 231\$.

Your goal is to implement this sequence, by returning each element as a multiple of nine. For example, the first 23 elements of this sequence are:

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

Some other test cases (0 indexed):

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

Rules:

• The submission can be any of:
  • A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.
  • A program/function that takes a number \$n\$ and returns up to the \$n\$th index, either 0 or 1 indexed.
  • A program/function that outputs/returns the sequence infinitely.
• The program should be capable of theoretically handling up to the \$11!-1\$th element and beyond, though I understand if time/memory constraints make this fail. In particular, this means you cannot concatenate the digits and evaluate as base 10, since something like \$012345678910\$ would be wrong.
• This is code-golf, so the shortest implementation for each language wins!

Notes:

• This is OEIS A217626
• I am offering a bounty of 500 for a solution that works out the elements directly without calculating the actual permutations.
• The sequence works for any contiguous digits. For example, the differences between the permutations of \$ [1,2,3,4]_{10} \$ are the same as for \$[-4,-3,-2,-1]_{10}\$.

Answer 1

Jelly, 9 bytes

,‘œ?ŻḌI÷9

Try it online! (print the n'th element)

Try it online! (20 first elements)

Explanation:

      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 has the builtin œ? which computes the nth permutation of a list in approximately linear time. Quite useful.)

Answer 2

Charcoal, 71 bytes

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

Try it online! Link is to verbose version of code. Explanation:

≔⟦Ｎ⊕θ⟧η

Get a list containing the input and one more than the input.

Ｗ⌈η

Repeat until both values are zero.

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

Perform factorial base conversion on both values. This is the first time I've actually used ≧ on a list!

≔⁰δ

Clear the result.

Ｆ²«

Loop over each factorial base number.

≔Ｅυλζ

Make a list of the digits from 0 to length - 1.

≔⟦⟧η

Initialise the result to an empty list.

Ｆ⮌Ｅυ§κι«

Loop over the digits of the factorial base number.

⊞η§ζκ

Add the next permutation digit to the result.

≔Φζ⁻μκζ»

Remove that digit from the list.

≦⁻↨ηχδ»

Convert the permutation as a base 10 number and subtract the result so far from it.

Ｉ÷δ⁹

Divide the final result by 9 and cast to string.

Answer 3

Perl 6, 82 bytes

-2 bytes thanks to Jo King

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

Try it online!

0-indexed. Doesn't enumerate all permutations. Should theoretically work for all n, but bails out for n > 65536 with "Too many arguments in flattening array".

The following 80 byte version works for n up to 98!-2 and is a lot faster:

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

Try it online!

The following 53 byte version should theoretically work for all n, but bails out for n >= 20 with "refusing to permutate more than 20 elements".

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

Try it online!

Answer 4

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

Try it online!

1-indexed.

@guest271314's opinion is right. Direct permutation computation is shorter...

Explanation

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
)

Original solution (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

Try it online!

Link is to a longer version made for performance. Array(n+1) becomes Array(Math.min(n+1,15)) in order to make demo work. Theoretically works up to infinity (up to stack limit in practice).

Explanation

I mean there's too much to explain.

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

Answer 5

Pyth, 15 14 bytes

.+m/i.PdSQT9,h

Returns the nth term. Try it here.

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

Answer 6

J, 44, 41 bytes

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

Try it online!

Note: works even for 10! test case, but loses some precision there...

original explanation

(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

Answer 7

JavaScript (ES6), 112 bytes

Very similar to Shieru Asakoto's algorithm.

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)

Try it online!