13
\$\begingroup\$

An alternating permutation is a permutation of the first \$ n \$ integers \$ \{ 1 ... n \} \$, such that adjacent pairs of values in the permutation alternate between increasing and decreasing (or vice versa).

Equivalently, it is a permutation where there are no "runs" of continuously increasing or decreasing values with a length \$ > 2 \$.

For example, 2 4 1 5 3 6 is an alternating permutation for \$ n = 6 \$, because \$ 2 < 4 \$, and \$ 4 > 1 \$, and \$ 1 < 5 \$, and \$ 5 > 3 \$, and \$ 3 < 6 \$: each pair alternates in their relative comparisons.

However, 1 3 2 4 6 5 is not a valid alternating permutation, because it contains the continuously increasing sequence 2 4 6 (\$ 2 < 4 \$ and \$ 4 < 6 \$).

In this challenge we will consider the number of alternating permutations for a given positive integer \$ n \$.

For example, for \$ n = 4 \$, there are \$ 4! = 24 \$ permutations, of which \$ 10 \$ are alternating permutations:

1 3 2 4
1 4 2 3
2 1 4 3
2 3 1 4
2 4 1 3
3 1 4 2
3 2 4 1
3 4 1 2
4 1 3 2
4 2 3 1

You may notice that every permutation has a duplicate which is just its reverse. Thus, for this challenge, when there is a pair of permutations which are the reverses of each other, you should only count it once.

Note that for \$ n = 1 \$, there is only one permutation, just 1, which doesn't have a distinct reverse. So for \$ n = 1 \$, the output is still \$ 1 \$.

For \$ n = 0 \$, there is also only one permutation, the empty one, but you do not need to handle it (we only care about \$ n \ge 1 \$).

Your task, finally, is to output the sequence of the number of alternating permutations for positive integers \$ n \$, excluding reverse-duplicates. This sequence starts:

1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765

This is A000111 (after \$ n = 0 \$) in the OEIS, and it is half of A001250 (after \$ n = 1 \$).

Rules

  • As with standard challenges, you may choose to either:
    • Take an input \$ n \$ and output the \$ n \$th term in the sequence
    • Take an input \$ n \$ and output the first \$ n \$ terms
    • Output the sequence indefinitely, e.g. using a generator
  • You may use \$ 0 \$- or \$ 1 \$-indexing
  • You may use any standard I/O method
  • Standard loopholes are forbidden
  • This is , so the shortest code in bytes wins
\$\endgroup\$
4
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – pxeger
    Jun 3 at 5:34
  • \$\begingroup\$ I dislike the reversal requirement, as this is simply going to add a byte or two to each answer halving the final result. \$\endgroup\$
    – emanresu A
    Jun 3 at 5:46
  • 2
    \$\begingroup\$ @emanresuA spoiler alert: there are better methods to compute the answer than by actually generating and filtering all the permutations. \$\endgroup\$
    – pxeger
    Jun 3 at 6:06
  • \$\begingroup\$ This is the Boustrophedon transform of the sequence 1,0,0,0,.... \$\endgroup\$
    – alephalpha
    Jun 4 at 12:34

12 Answers 12

9
\$\begingroup\$

Python 3.8, 54 bytes

-4 bytes thanks to @ovs
-2 bytes thanks to @Albert.Lang

Prints the sequence indefinitely.

s,*a=1,
while[print(s)]:a=s,*[s:=s+x for x in a[::-1]]

Try it online!

Explanation

I originally found this method in one of the Python implementations on the OEIS page. Here is a simple explanation of how it works.

The alternating permutation in this problem can be viewed as a chain of alternating less-than and greater-than signs such that it begins with >: ? > ? < ? > ? < .... Let \$ P(n,e) \$ be the number of alternating permutations of size \$ n \$ whose last element is \$ e \$. Given this, the number of alternating permutations of size \$ n \$ is simply \$ \sum_{i=1}^n P(n,i) \$. Our goal now is to come up with a convenient algorithm to compute \$ P \$.

Let's take the example \$ P(5,4) \$, for which the permutation would be in the form:

? > ? < ? > ? < 4

Now, the number to the left of the 4 must be either 1, 2, or 3, while the rest of the numbers will be from the set {1, 2, 3, 5}. In other words, the four unknown numbers must form an alternating permutation whose last element is between 1 and 3. This however, is exactly the same as asking the answer to \$ P(4,1) + P(4,2) + P(4,3) \$. One might argue that there is a difference in that the missing numbers do not necessarily form a permutation from 1 to n. However, as long as they are all distinct, this will not matter, since comparisons only care about the relative ordering of the numbers.

More generally, we can say that \$ P(n,e) = \sum_{i=1}^{e-1} P(n-1,i) \$. But, this formula only makes sense if the rightmost comparison is a < (odd \$ n \$). Instead if it were a > (even \$ n \$), we would have \$ P(n,e) = \sum_{i=e+1}^{n} P(n-1,i) \$.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 56 bytes by printing s instead of sum(a). \$\endgroup\$
    – ovs
    Jun 3 at 7:00
  • \$\begingroup\$ @ovs Of course! I remember being blinded by the same trick in another golf a few months ago. Clearly I haven't learned. \$\endgroup\$ Jun 3 at 7:07
  • 3
    \$\begingroup\$ 54 bytes \$\endgroup\$ Jun 3 at 8:37
5
\$\begingroup\$

R, 36 35 bytes

while(T<-rev(diffinv(T)))show(T[1])

Try it online!

Port of @dingledooper's answer.

\$\endgroup\$
5
\$\begingroup\$

PARI/GP, 23 bytes

n->2*abs(polylog(-n,I))

Attempt This Online!

Based on the PARI/GP code on OEIS by M. F. Hasler.


PARI/GP, 35 bytes

n->Vec(1/(1-sin(x+O(x^n))))[n]*n--!

Attempt This Online!

The exponential generating function of the sequence is \$1/(1-\sin(x))\$.

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

APL (Dyalog Unicode), 12 bytes

Full program. Port of dingledooper's answer.

⊃(⌽0,+\)⍣⎕,1

Try it online!


31 bytes:

{1<⍵:2÷⍨(k!⍵-1)+.××∘⌽⍨∇¨k←⍳⍵⋄1}

Try it on APLgolf!

Implements a formula from OEIS:

$$ 2\times a(n+1) = \sum_{k=0..n} {n \choose k}\times a(k)\times a(n-k) $$


31 bytes:

{+/2((-\⍳⍵-1)≡⍥×-/)¨∪⍋⍤,¨,⍳⍴⍨⍵}

Try it on APLgolf!

Generates all permutations and counts the alternating ones that start with an increment.

\$\endgroup\$
7
  • \$\begingroup\$ What do you mean by "alternating ones that start with an increment"? I'm just wondering how you distinguish between, say, "1, 4, 3, 5, 2" and "2, 5, 3, 4, 1". \$\endgroup\$
    – Neil
    Jun 3 at 7:30
  • \$\begingroup\$ Also, @dingledooper's answer is just another of the formulas on OEIS; at least, that's where I got it from. \$\endgroup\$
    – Neil
    Jun 3 at 7:32
  • \$\begingroup\$ @Neil I generate all unique permutations, then check for each if the signs of the deltas follow 1,-1,1,-1,.... \$\endgroup\$
    – ovs
    Jun 3 at 7:34
  • 1
    \$\begingroup\$ Ah, I see I had actually scrolled down to the "Maple" section; A000111(n)=S(n,n) where S(0,0)=1, S(n,0)=0 and S(n,k)=S(n,k-1)+S(n-1,n-k) i.e. zero-prefixed cumulative sum of reverse of previous row. \$\endgroup\$
    – Neil
    Jun 3 at 7:48
  • 1
    \$\begingroup\$ I see what you mean now. I count both, but exactly half of the alternating permutations start with an increment, so I'm excluding a different half of the permutations than the challenge specification. Both lead to the same result \$\endgroup\$
    – ovs
    Jun 3 at 7:48
3
\$\begingroup\$

Charcoal, 22 bytes

⊞υ¹FN≔⊞O⮌EυΣ…υ⊕λ⁰υI§υ⁰

Try it online! Link is to verbose version of code. Works for n=0. Explanation: Uses a formula from OEIS.

⊞υ¹

Start with the empty permutation.

FN

Repeat n times.

≔⊞O⮌EυΣ…υ⊕λ⁰υ

Take the cumulative sums of the list, reverse the result, and append a zero.

I§υ⁰

Output the first element of the final list.

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

05AB1E, 9 8 bytes

$F0).sO`

Port of @dingledooper's Python answer, but outputs the \$n^{th}\$ value instead to save a byte.

Try it online or verify the first 25 test cases.

Outputting the infinite sequence for a direct port would be:

1[0ª.sO¤,

Try it online.

Explanation:

$         # Push 1 and the input
 F        # Pop and loop the input amount of times:
  0       #  Push a 0
   )      #  Wrap the entire stack into a list
    .s    #  Get the suffixes of this list
      O   #  Sum each inner suffix-list
       `  #  Pop and push all values to the stack
          # (after the loop, the top value is output implicitly as result)
1         # Start with 1
 [        # Loop indefinitely:
  0ª      #  Append 0 to the current list (convert an integer to a digit-list
          #  before appending, which happens for the 1 in the first iteration)
    .s    #  Get the suffixes of this list
      O   #  Sum each inner suffix-list
       ¤  #  Push the last integer (without popping the list)
        , #  Pop and output it with trailing newline
\$\endgroup\$
3
\$\begingroup\$

Haskell + hgl, 22 bytes

he<ix(rS(+)<he*^rv)[1]

This uses the by Chai Wah Wu that everyone else is using. It produces an infinite list of the results in order.

Explanation

First we have the iterative step rS(+)<he*^rv this gives the cumulative sums of the first element with the list reversed. With ix we iterate this infinitely starting with [1]. Then from there we just get the head of every element in the list with he.

New method, 25 bytes

cn(mF~<lt3<<fce)<tv e1<e1

This method isn't new, but it hasn't been used here yet and it's pretty neat. And it's rather close to edging out the Chai Wah Wu method.

Explanation

From the comments on the OEIS:

Number of sequences (e(1), ..., e(n-1)), 0 <= e(i) < i, such that no three terms are equal. [Theorem 7 of Corteel, Martinez, Savage, and Weselcouch] - Eric M. Schmidt, Jul 17 2017

First we use e1 to get the range from \$1\$ to \$n\$. The next step is tv e1 which is a little hard to explain, because tv is fundamentally a pretty weird operation. Instead we can talk about the equivalent but slightly longer sQ<m e1. m e1 maps e1 across the lists to creates ranges of increasing size. sQ creates a list of ways to pick one element in order from each list.

So the result now is all the non-negative integer sequences whose values are smaller than their indexes. Now we count all the ones that don't have any value repeated 3 times. cn will take a predicate and count the number of elements satisfying that predicate so we use that. Now we just need a predicate that says "Contains no element 3 or more times". One way to do this is

pred x = mF(lt3<fce x)x

Here fce counts the number of times an element appears in a list, add it with lt3 and lt3<fce x says "does this element appear less than three times in x". We use mF to collect the result of running this over every element of x, so it says "does all the elements of x appear less than 3 times in x". Now we use a bit of monad magic t make this point free and we have mF~<lt3<<fce.

Naive method, 31 bytes

dv2<P1<cn(fo<pa nq<pa cp)<pm<e0

Explanation

First we get all the permutations of size \$n+1\$. Now we count the satisfactory permutations with cn. To determine if a permutation is satisfactory we first compare consecutive elements pa cp. This gets us the direction of each change between elements, if there are two consecutive equal elements now that means that there is a run of 3 which is monotonic, and thus that permutation is invalid, so we use pa nq to compare the consecutive elements and fo to ensure they are all unequal.

Once we've counted those we need to divide by two, rounding up. Do do this I do the old plus 1, divide by 2 trick. dv2>P1

Reflections

The nice thing about this problem is there are many ways to approach it. Since I've tried this so many ways I have gotten quite a bit of useful reflection out of this.

Reflections on the Chai Wah Wu method

Overall this is the method with the least room for improvement. hgl doesn't seem to have any major gaps.

  • rS(+) which gives the cumulative sums might be worth having a short hand. Hard to say.
  • [1] is a little long, but I'm not sure if it's worth having a 2 bytes shorthand especially, when [1] never needs any whitespace padding while an alias would.

Reflections on the new method

  • While I was working on this I found a bug with mL and related functions. It wouldn't have hurt this answer even if I went with the strategy that used those functions, but it was confusing and should be fixes.
  • There aren't really many functions having to do with sub-sequences. Originally I had tried to get all the subsequences longer than 3 and check that none of them contained only 1 type of element. However the only subsequence function was ss which just gets all the subsequences. If I had a function ss3 which gets subsequences of size 3, then this could be
    cn(no lq<ss3)<tv e1<e1
    
    which would have been 3 bytes shorter tying it with the shortest method. But moreover there should just be more than one function dealing with sub-sequences.

Relfections on the naive method

  • There should be a shorthand for "all permutations of n elements". pm<e1 is the shortest way to achieve that right now. Would save 2 bytes overall.
  • It might also be nice to have a "permutations such that" function, however it would need to be 2 bytes to save anything for this answer.
  • The naive method uses pa cp, and it's not even the first time I've used pa cp. The alternative answer here uses pa cp and this change would have saved bytes there too. With a 3 byte name this would save 2 bytes here and 2 bytes on that answer.
  • dv2<P1 is abysmal. There should be a built in for integer division rounding up. It would save another 3 bytes on the naive approach, which if combined with the above would put it much more on par with other methods.
  • Doesn't make a difference here, but for a short bit I was frustrated that while we have ce, which counts the number of elements equal to some element, we don't have something which counts elements not equal to some element. Wouldn't have saved bytes here, but it's worth having.
\$\endgroup\$
3
\$\begingroup\$

HOPS, 7 bytes

bous(1)

Attempt This Online!

This sequence is the Boustrophedon transform of the sequence \$1,0,0,0,\dots\$.

HOPS is an extremely powerful language for integer sequences. To print the first 20 terms (0-indexed) of the sequence, just run hops --prec=20 "bous(1)"

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

Factor, 50 bytes

[ { 1 } [ 0 suffix reverse cum-sum ] repeat last ]

Try it online!

Returns the (1-indexed) \$n\$th term in the sequence. It uses dingledooper's method, but a comment by @Neil is what I based this answer on: "zero-prefixed cumulative sum of reverse of previous row."

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

C (gcc), 106 105 bytes

*a;*b;c;i;j;f(n){a=calloc(n,8);for(*a=i=1;n/i;++i,a=b)for(b=calloc(n,8),j=i,c=0;j--;)b[i-j]=c+=a[j];n=c;}

Try it online!

Uses the same method dingledooper explains in his Python answer.
Saved a byte thanks to ceilingcat!!!

Inputs a positive integer \$n\$.
Returns the \$1\$-based \$n^\text{th}\$ element of the sequence.

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

JavaScript (V8), 55 bytes

A port of dingledooper's algorithm.

A full program that prints the sequence forever.

for(a=[s=1];;)a=[s,...a.reverse(print(s)).map(x=>s+=x)]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 11 bytes

ɾṖƛ¯±¯A;∑½⌈

Try it Online!

The ½⌈ is because of the requirement to handle reversed lists.

ɾṖ          # Permutations of 1...n
  ƛ    ;∑   # Count where...
     ¯      # Deltas of... 
    ±       # Signs of ...
   ¯        # Deltas
      A     # Are all nonzero
         ½⌈ # Halve the final result and round up

The is-alternating code ¯±¯A works because, for example with [1, 6, 2, 4, 3]:

¯    # Deltas - [5, -4, 2, -1] - Signs should be alternating
 ±   # Signs - [1, -1, 1, -1] - Should be list of alternating 1s and -1s
  ¯  # Deltas - [-2, 2, -2] - If there are two consecutive equal values in ^ there should be a 0
   A # All - 1 - if and only if there's no zeroes in ^ the list is alternating.
\$\endgroup\$
2
  • \$\begingroup\$ Legit pro at vyxal! \$\endgroup\$
    – DialFrost
    Jun 3 at 6:13
  • \$\begingroup\$ With the R flag, you can yeet ɾ \$\endgroup\$
    – Steffan
    Jun 3 at 16:21

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.