# 9erilous 9ermutations

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$/extract_tex]. 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 , 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}\$$. • What's the tie breaker for the bounty? – nwellnhof Nov 11 '18 at 10:08 • There is little point in "work out the elements directly" since computing the permutation itself takes linear time (in the size of the input) (right?), which is pretty good already. You just want to see cool methods? – user202729 Nov 11 '18 at 13:41 • Another interesting test case is \10!-1\ (3628799 => -83676269) which I think is the first negative term. – nwellnhof Nov 11 '18 at 14:18 • @user202729 Maybe the OP wants some log time or constant time algorithm? Because this is an OEIS sequence, such an algorithm may help research. – Shieru Asakoto Nov 13 '18 at 3:44 • @user202729 I know, because basically we just need \O(\Gamma^{-1}(n))\ steps. But I'd also like to know whether there's a log(log(n)) or constant time algorithm – Shieru Asakoto Nov 13 '18 at 4:42 ## 7 Answers # 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.) # 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. # 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! # 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  • FWIW, Given that this implementation does not return all differences up to n, this solution stackoverflow.com/a/34238979 provides a means to get two adjacent permutations, or number representations of permutations directly by index, which when golfed, should reduce the necessary code to produce the output (f(n) - f(n-1))/9 for this selected answer type consistent with the rule "A program/function that takes a number and returns the number at that index, either 0 or 1 indexed.". – guest271314 Nov 19 '18 at 5:27 # 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  # 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. 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 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!