8
\$\begingroup\$

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 , 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}\$.
\$\endgroup\$
  • \$\begingroup\$ What's the tie breaker for the bounty? \$\endgroup\$ – nwellnhof Nov 11 '18 at 10:08
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – user202729 Nov 11 '18 at 13:41
  • 1
    \$\begingroup\$ Another interesting test case is \$10!-1\$ (3628799 => -83676269) which I think is the first negative term. \$\endgroup\$ – nwellnhof Nov 11 '18 at 14:18
  • \$\begingroup\$ @user202729 Maybe the OP wants some log time or constant time algorithm? Because this is an OEIS sequence, such an algorithm may help research. \$\endgroup\$ – Shieru Asakoto Nov 13 '18 at 3:44
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – Shieru Asakoto Nov 13 '18 at 4:42
5
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

Charcoal, 71 bytes

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

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

≔⟦N⊕θ⟧η

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

W⌈η

Repeat until both values are zero.

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

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

≔⁰δ

Clear the result.

F²«

Loop over each factorial base number.

≔Eυλζ

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

≔⟦⟧η

Initialise the result to an empty list.

F⮌Eυ§κι«

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.

I÷δ⁹

Divide the final result by 9 and cast to string.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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.". \$\endgroup\$ – guest271314 Nov 19 '18 at 5:27
2
\$\begingroup\$

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
\$\endgroup\$
2
+150
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.