34
\$\begingroup\$

While doodling around with numbers, I found an interesting permutation you can generate from a list of numbers. If you repeat this same permutation enough times, you will always end up back at the original array. Let's use the following list:

[1, 2, 3, 4, 5]

as an example

  1. Reverse the array. Now our array is

    [5, 4, 3, 2, 1]
    
  2. Reorder (swap) each pair. Our list has 2 pairs: [5, 4], and [3, 2]. Unfortunately, we can't group the 1 into a pair, so we'll just leave it on it's own. After swapping each pair, the new array is:

    [4, 5, 2, 3, 1]
    
  3. Repeat steps 1 and 2 until we return to the original array. Here are the next 4 steps:

    Step 2:
    Start:          [4, 5, 2, 3, 1]
    Reversed:       [1, 3, 2, 5, 4]
    Pairs Swapped:  [3, 1, 5, 2, 4]
    
    Step 3:
    Start:          [3, 1, 5, 2, 4]
    Reversed:       [4, 2, 5, 1, 3]
    Pairs Swapped:  [2, 4, 1, 5, 3]
    
    Step 4:
    Start:          [2, 4, 1, 5, 3]
    Reversed:       [3, 5, 1, 4, 2]
    Pairs Swapped:  [5, 3, 4, 1, 2]
    
    Step 5:
    Start:          [5, 3, 4, 1, 2]
    Reversed:       [2, 1, 4, 3, 5]
    Pairs Swapped:  [1, 2, 3, 4, 5]
    
    # No more steps needed because we are back to the original array
    

    If the length of the list, n is odd, it will always take exactly n steps to return to the original array. If n is even, it will always take 2 steps to return to the original array, unless n is 2, in which case it will take 1 step (because reversing and swapping is the same thing).

Your task for today (should you choose to accept it) is to visualize this set of steps for lists of arbitrary lengths. You must write a program or function that takes a single positive integer n as input, and does this set of steps for the list [1, n]. You must output each intermediate step along the way, whether that means printing each step, or returning them all as a list of steps. I'm not very picky about the output format, as long as it's clear that you are generating every step. This means (for example) any of these:

  • Outputting every step as a list to STDOUT

  • Returning a list of lists

  • Returning a list of string representations of each step

  • Returning/outputting a matrix

would be acceptable.

You must also output the original array, whether that comes at the end or at the beginning is up to you. (technically, both are correct)

You will have to handle the edge case of 2 taking 1 step instead of 2, so please make sure your solution works with an input of 2 (and 1 is another potential edge case).

As usual, this is , so standard loopholes apply, and try to make your solution shorter than any other in the language of your choice (or even try to beat another language that is typically shorter than yours if you're feeling up for a challenge).

Test IO

1: 
[1]


2: 
[1, 2]


3: 
[2, 3, 1]
[3, 1, 2]
[1, 2, 3]


4: 
[3, 4, 1, 2]
[1, 2, 3, 4]


5: 
[4, 5, 2, 3, 1]
[3, 1, 5, 2, 4]
[2, 4, 1, 5, 3]
[5, 3, 4, 1, 2]
[1, 2, 3, 4, 5]


7: 
[6, 7, 4, 5, 2, 3, 1]
[3, 1, 5, 2, 7, 4, 6]
[4, 6, 2, 7, 1, 5, 3]
[5, 3, 7, 1, 6, 2, 4]
[2, 4, 1, 6, 3, 7, 5]
[7, 5, 6, 3, 4, 1, 2]
[1, 2, 3, 4, 5, 6, 7]


9: 
[8, 9, 6, 7, 4, 5, 2, 3, 1]
[3, 1, 5, 2, 7, 4, 9, 6, 8]
[6, 8, 4, 9, 2, 7, 1, 5, 3]
[5, 3, 7, 1, 9, 2, 8, 4, 6]
[4, 6, 2, 8, 1, 9, 3, 7, 5]
[7, 5, 9, 3, 8, 1, 6, 2, 4]
[2, 4, 1, 6, 3, 8, 5, 9, 7]
[9, 7, 8, 5, 6, 3, 4, 1, 2]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

And for good measure, here's one giant test case:

27: 
[26, 27, 24, 25, 22, 23, 20, 21, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 1]
[3, 1, 5, 2, 7, 4, 9, 6, 11, 8, 13, 10, 15, 12, 17, 14, 19, 16, 21, 18, 23, 20, 25, 22, 27, 24, 26]
[24, 26, 22, 27, 20, 25, 18, 23, 16, 21, 14, 19, 12, 17, 10, 15, 8, 13, 6, 11, 4, 9, 2, 7, 1, 5, 3]
[5, 3, 7, 1, 9, 2, 11, 4, 13, 6, 15, 8, 17, 10, 19, 12, 21, 14, 23, 16, 25, 18, 27, 20, 26, 22, 24]
[22, 24, 20, 26, 18, 27, 16, 25, 14, 23, 12, 21, 10, 19, 8, 17, 6, 15, 4, 13, 2, 11, 1, 9, 3, 7, 5]
[7, 5, 9, 3, 11, 1, 13, 2, 15, 4, 17, 6, 19, 8, 21, 10, 23, 12, 25, 14, 27, 16, 26, 18, 24, 20, 22]
[20, 22, 18, 24, 16, 26, 14, 27, 12, 25, 10, 23, 8, 21, 6, 19, 4, 17, 2, 15, 1, 13, 3, 11, 5, 9, 7]
[9, 7, 11, 5, 13, 3, 15, 1, 17, 2, 19, 4, 21, 6, 23, 8, 25, 10, 27, 12, 26, 14, 24, 16, 22, 18, 20]
[18, 20, 16, 22, 14, 24, 12, 26, 10, 27, 8, 25, 6, 23, 4, 21, 2, 19, 1, 17, 3, 15, 5, 13, 7, 11, 9]
[11, 9, 13, 7, 15, 5, 17, 3, 19, 1, 21, 2, 23, 4, 25, 6, 27, 8, 26, 10, 24, 12, 22, 14, 20, 16, 18]
[16, 18, 14, 20, 12, 22, 10, 24, 8, 26, 6, 27, 4, 25, 2, 23, 1, 21, 3, 19, 5, 17, 7, 15, 9, 13, 11]
[13, 11, 15, 9, 17, 7, 19, 5, 21, 3, 23, 1, 25, 2, 27, 4, 26, 6, 24, 8, 22, 10, 20, 12, 18, 14, 16]
[14, 16, 12, 18, 10, 20, 8, 22, 6, 24, 4, 26, 2, 27, 1, 25, 3, 23, 5, 21, 7, 19, 9, 17, 11, 15, 13]
[15, 13, 17, 11, 19, 9, 21, 7, 23, 5, 25, 3, 27, 1, 26, 2, 24, 4, 22, 6, 20, 8, 18, 10, 16, 12, 14]
[12, 14, 10, 16, 8, 18, 6, 20, 4, 22, 2, 24, 1, 26, 3, 27, 5, 25, 7, 23, 9, 21, 11, 19, 13, 17, 15]
[17, 15, 19, 13, 21, 11, 23, 9, 25, 7, 27, 5, 26, 3, 24, 1, 22, 2, 20, 4, 18, 6, 16, 8, 14, 10, 12]
[10, 12, 8, 14, 6, 16, 4, 18, 2, 20, 1, 22, 3, 24, 5, 26, 7, 27, 9, 25, 11, 23, 13, 21, 15, 19, 17]
[19, 17, 21, 15, 23, 13, 25, 11, 27, 9, 26, 7, 24, 5, 22, 3, 20, 1, 18, 2, 16, 4, 14, 6, 12, 8, 10]
[8, 10, 6, 12, 4, 14, 2, 16, 1, 18, 3, 20, 5, 22, 7, 24, 9, 26, 11, 27, 13, 25, 15, 23, 17, 21, 19]
[21, 19, 23, 17, 25, 15, 27, 13, 26, 11, 24, 9, 22, 7, 20, 5, 18, 3, 16, 1, 14, 2, 12, 4, 10, 6, 8]
[6, 8, 4, 10, 2, 12, 1, 14, 3, 16, 5, 18, 7, 20, 9, 22, 11, 24, 13, 26, 15, 27, 17, 25, 19, 23, 21]
[23, 21, 25, 19, 27, 17, 26, 15, 24, 13, 22, 11, 20, 9, 18, 7, 16, 5, 14, 3, 12, 1, 10, 2, 8, 4, 6]
[4, 6, 2, 8, 1, 10, 3, 12, 5, 14, 7, 16, 9, 18, 11, 20, 13, 22, 15, 24, 17, 26, 19, 27, 21, 25, 23]
[25, 23, 27, 21, 26, 19, 24, 17, 22, 15, 20, 13, 18, 11, 16, 9, 14, 7, 12, 5, 10, 3, 8, 1, 6, 2, 4]
[2, 4, 1, 6, 3, 8, 5, 10, 7, 12, 9, 14, 11, 16, 13, 18, 15, 20, 17, 22, 19, 24, 21, 26, 23, 27, 25]
[27, 25, 26, 23, 24, 21, 22, 19, 20, 17, 18, 15, 16, 13, 14, 11, 12, 9, 10, 7, 8, 5, 6, 3, 4, 1, 2]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27]

Have fun golfing!

\$\endgroup\$
6
  • 6
    \$\begingroup\$ Is it fine to generate the original range at the front? \$\endgroup\$
    – hyper-neutrino
    Commented Sep 27, 2017 at 2:44
  • 1
    \$\begingroup\$ I think there's an error in the last line in the example. It should be 1 2 3 4 5, not 1 2 4 3 5. \$\endgroup\$ Commented Sep 27, 2017 at 6:42
  • 2
    \$\begingroup\$ Can anyone confirm that element 0 will only ever be 1 at the start and end of the process? \$\endgroup\$ Commented Sep 27, 2017 at 10:20
  • 1
    \$\begingroup\$ @RobertoGraham I have a python script that verifies that array[0] will only be 1 at the start and end of the process up to n = 999. From looking at the pattern, it seems like for every odd n, the first element goes 1, n-1, 3, n - 3, 5, n - 5, 7... up until n - 2, 3, n, 1, which will always take n steps. I don't see any reason that this pattern would change with larger n. \$\endgroup\$
    – DJMcMayhem
    Commented Sep 27, 2017 at 17:00
  • 3
    \$\begingroup\$ If we want to prove that the period is n when n is odd, it's probably easier to track where the element 1 goes: it follows the path 1, n, 2, n-2, 4, n-4, 6, n-6, 8, n-8, ... and it's easy to show by induction that an element at even position x moves to n-x after one step, and an element at odd position x moves to n-x+2. So if n=2k+1, then after the 2k-th step 1 will be be at 2k, and on the next step at n-2k = 1. \$\endgroup\$ Commented Sep 27, 2017 at 20:33

25 Answers 25

16
\$\begingroup\$

TI-Basic (83 series), 58 57 54 bytes (104 characters)

:seq(I,I,1,Ans→A
:Ans→B
:Repeat prod(Ans=ᶫB
:ᶫB→C
:int(⁻Ans/2→D
:SortD(ᶫC,ᶫA
:SortD(ᶫD,ᶫA
:Pause ᶫA
:End

Explanation

Takes input in Ans (e.g., write 5:prgmNAME to use lists of size five).

Creates three auxiliary lists of the given size (which are recreated from ᶫB at each step): ᶫB = ᶫC = {1,2,3,4,5,...} and ᶫD = {-1,-1,-2,-2,-3,...}. At each step, sorts ᶫC and ᶫD in descending order, applying the same permutation to ᶫA. In the case of ᶫC, this reverses ᶫA, and in the case of ᶫD, this swaps adjacent pairs because TI-Basic uses a really stupid selection sort implementation for SortD( which reorders as many identical elements as it possibly can. When ᶫA is equal to ᶫB again, we stop.

No, seriously, their built-in sorting algorithm is my second-biggest complaint with the TI-Basic interpreter. (My biggest complaint is how lots of nested loops slow down the interpreter, since the loop data is stored in a stack, but the stack is grown from the wrong end, so the calculator has to move the entire stack every time an element is pushed or popped.) But this time, it's convenient.


-1 byte: Pause stores the value it's printing to Ans, which is shorter to reference than ᶫA.

-3 bytes: take input in Ans

\$\endgroup\$
1
  • \$\begingroup\$ Awesome trick with the selection sort! \$\endgroup\$
    – Riking
    Commented Sep 28, 2017 at 4:23
7
\$\begingroup\$

Jelly, 10 bytes

RµUs2UFµÐĿ

Try it online!

Explanation

RµUs2UFµÐĿ  Main link
R           Generate the range
        ÐĿ  While the results are unique (collecting results)
 µUs2UFµ    Reverse and reorder
  U         Reverse
   s        Slice non-overlapping into length
    2       2
     U      Reverse (automatically vectorizes to depth 1)
      F     Flatten

Note

If the original range needs to be at the end, append ṙ1 to the code for 12 bytes.

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

05AB1E, 13 11 bytes

LIGÂ2ôí˜})Ù

Try it online!

Explanation

L             # range [1 ... input]
 IG           # input-1 times do:
   Â          # bifurcate
    2ô        # split into pieces of 2
      í       # reverse each
       ˜      # flatten
        }     # end loop
         )    # wrap stack in a list
          Ù   # remove duplicates
\$\endgroup\$
0
4
\$\begingroup\$

JavaScript (ES6), 89 85

Edit 4 bytes saved thx @JustinMariner

Using the fact that when any element is at the right place, all elements are.

n=>{for(l=[];n;l[n-1]=n--);while(alert(l=l.reverse().map((x,i)=>l[i^1]||x)),l[0]-1);}

Less golfed

n => {
  for(l=[], i=0; i<n; l[i] = ++i);
  while( alert(l=l.reverse().map( (x,i) => l[i^1] || x)),
         l[0]-1);
}

Test

var F=
n=>{for(l=[];n;l[n-1]=n--);while(alert(l=l.reverse().map((x,i)=>l[i^1]||x)),l[0]-1);}

alert=x=>console.log(x+'') // to avoid popup stress

function update() {
  F(+I.value);
} 

update()
<input type=number id=I value=1 min=1 oninput='update()'>

\$\endgroup\$
2
  • \$\begingroup\$ I think you can shorten your range-building loop to for(l=[];n;l[n-1]=n--);, Try it online!. \$\endgroup\$ Commented Sep 27, 2017 at 15:49
  • \$\begingroup\$ @JustinMariner wow backwards, great! Thanks \$\endgroup\$
    – edc65
    Commented Sep 27, 2017 at 19:31
4
\$\begingroup\$

R, 109 95 94 79 74 62 bytes

If the fact that the code throws warnings on top of the actual solution (no warnings if n is 1, 3 warnings if n is even and n warnings if n is odd) is not an issue, then the following works similarly to the previous solution, thanks to vector recycling:

n=scan();m=1:n;w=0:n+2*1:0;while(print(m<-rev(m)[w[w<=n]])-1)n

Try it online!

Thanks again to @Giuseppe for an extra 12 bytes off!

Previous, warning-less solution at 94 bytes:

n=scan();m=s=1:n;while(any(print(m<-rev(m)[c(if(n>1)2:1+rep(seq(0,n-2,2),e=2),n[n%%2])])!=s))n

Try it online!

Original solution at 109 bytes:

n=scan();m=s=1:n;repeat{cat(m<-rev(m)[c(t(embed(s,min(n,2))[!!s[-n]%%2,]),n[n%%2])],"\n");if(all(m==s))break}

Try it online!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ 88 bytes -- print returns its argument so we can take advantage of it here. I don't think I'd ever seen encode before; that's a neat way of indexing! \$\endgroup\$
    – Giuseppe
    Commented Sep 27, 2017 at 13:49
  • \$\begingroup\$ Thanks! Though i will need to make it a tiny bit longer as it doesn't work if n=1 so far. \$\endgroup\$
    – plannapus
    Commented Sep 27, 2017 at 13:52
  • \$\begingroup\$ Oh, I didn't notice that...replace 2 in embed with min(n,2)? \$\endgroup\$
    – Giuseppe
    Commented Sep 27, 2017 at 13:55
  • 1
    \$\begingroup\$ you can just put n instead of {} for the while loop since n doesn't do anything. :) \$\endgroup\$
    – Giuseppe
    Commented Sep 27, 2017 at 13:57
  • 1
    \$\begingroup\$ Impressive improvement!!! 0:n+2*1:0 is the same as 1+0:n+c(1,-1) for -4 bytes. any(print(...) != s) is equivalent to any(print(...)-s) for -1 byte. Aaand if we can prove that m[1]==1 only at the end of the algorithm, then we can drop the any, so we get while(print(...)-1) and we can remove s, so we get 62 bytes, n=scan();m=1:n;w=0:n+2*1:0;while(print(m<-rev(m)[w[w<=n]])-1)n \$\endgroup\$
    – Giuseppe
    Commented Sep 27, 2017 at 15:48
3
\$\begingroup\$

Mathematica, 142 bytes

(h=Range@#;W={};For[i=1,i<=#,i++,s=Reverse@h;AppendTo[W,h=Join[f=Flatten[Reverse/@Partition[s,{2}]],s~Complement~f]];s=h];DeleteDuplicates@W)&
\$\endgroup\$
3
\$\begingroup\$

Husk, 9 bytes

U¡ȯṁ↔C2↔ḣ

Try it online!

            -- implicit input N                 |  3
         ḣ  -- list [1..N]                      | [1,2,3]
 ¡(     )   -- iterate the following function,  | [[1,2,3],[2,3,1],[3,1,2],[1,2,3],...
U           -- until the first repetition:      | [[1,2,3],[2,3,1],[3,1,2]]
       ↔    --   reverse                        |   [3,2,1]
     C2     --   cut into two                   |   [[3,2],[1]]
   ṁ↔       --   reverse each pair & flatten    |   [2,3,1]
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 79 bytes

f=(n,a=[...Array(n)],b=a.map((x,i)=>n-((x?x-1:i)^1)||1))=>b[0]>1?b+`
`+f(n,b):b

Outputs a list for each step.

Note that we don't need to initialize the array to get the ball rolling. If uninitialized (x is undefined), we can use the array's indices (parameter i) to do the first step:

b=a.map((x,i)=>n-((x?x-1:i)^1)||1)

Test Cases:

f=(n,a=[...Array(n)],b=a.map((x,i)=>n-((x?x-1:i)^1)||1))=>b[0]>1?b+`
`+f(n,b):b

console.log(f(1));
console.log(f(2));
console.log(f(3));
console.log(f(4));
console.log(f(5));
console.log(f(7));
console.log(f(27));

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

Japt, 20 18 15 12 bytes

õ
£=ò2n)ÔcÃâ

Try it (-R flag for visualisation purposes only)

1 byte saved thanks to ETHproductions.

               :Implicit input of integer U
õ              :Range [1,U]
\n             :Reassign to U
£              :Map
  ò            :  Partitions
   2           :    Of length 2
    n          :    Starting from the end
     )         :  End partition
      Ô        :  Reverse
       c       :  Flatten
 =             :  Reassign to U
        Ã      :End map
         â     :Deduplicate
\$\endgroup\$
2
  • \$\begingroup\$ As of just now, I believe w ò mw can be ò2n)w \$\endgroup\$ Commented Sep 27, 2017 at 19:08
  • \$\begingroup\$ Oo, nice one, thanks, @ETHproductions. About to walk into the pub so I'll have a proper look at that in the morn'. \$\endgroup\$
    – Shaggy
    Commented Sep 27, 2017 at 20:35
2
\$\begingroup\$

Ruby, 64 57 52 50 bytes

->x{(s=*w=1..x).map{s=w.map{|y|s[-y^1]||s[0]}}|[]}

Try it online!

How it works:

First create the range, then repeat the permutation x times: use a negative index, but flip the last bit, so we get the sequence -2, -1, -4, -3... if x is even, this will end well, if not we will add the remaining element at the end. Last step: filter out repeated arrays (so we cover all cases: x=1, x=2, odd and even numbers)

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

Haskell, 75 74 bytes

g(a:b:c)=b:a:g c
g x=x
h=g.reverse
0!x|x<[2]=[x]|1<2=x:0!h x
p n=0!h[1..n]

Try it online!

g does the pair-wise swaps, h a single step (reverse + reorder), ! repeatedly applies h (and collects the intermediate results) until the order is restored. Note: ! takes the additional but unused extra parameter 0 just to make it an infix operator. The main function p starts it up.

Edit: Thanks to @Angs for a byte.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 0!x instead of f x saves a byte - Try it online! \$\endgroup\$
    – Angs
    Commented May 12, 2018 at 17:04
2
\$\begingroup\$

Stax, 17 bytes

âΩÄ─g╫B♥C╛♠ƒ?|πcD

Run and debug it

Explanation

RX~Wr2/{r+}Fc|uPcx=C      # Full program, unpacked, implicit input
RX~                       # Create range, save to X register, pop back to input stack
   W                      # Start while loop until truthy value
    r                     # reverse array
     2/                   # Split into groups of 2
      {r+}F               # Loop through each set and reverse each
           c              # Copy top value
            |u            # Convert to string representation of array
              P           # Pop top value off
               cx=        # Copy top value, get value of x register, compare to top value
                  C       # If top value is truthy, cancel block and end

Suprised it works as fast as it does, tested up to 399 before I didn't want to temp my browser anymore.

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

Java 8, 215 214 bytes

import java.util.*;n->{Stack a=new Stack(),t;int i=0;for(;i<n;a.add(++i));t=(Stack)a.clone();Collections x=null;for(i=0;i<1|!a.equals(t);System.out.println(t))for(x.reverse(t),i=0;i<n;i++)if(i<n-1)x.swap(t,i,++i);}

I tried to golf it using actual arrays instead of a List, but both reversing and swapping will take up too many bytes.. Maybe it can be combined in one loop (instead of first reversing, then swapping), but I've yet to figure this out.
This can definitely be golfed some more, though.

Explanation:

Try it here.

import java.util.*;           // Required import for Stack and Collections

n->{                          // Method with integer parameter and no return-type
  Stack a=new Stack(),        //  Original List
        t;                    //  Copy-List
  int i=0;                    //  Index-integer, starting at 0
  for(;i<n;a.add(++i));       //  Fill the original list with the integers
  t=(Stack)a.clone();         //  Make a copy of the List
  Collections x=null;         //  Static `Collections` to reduce bytes
  for(i=0;                    //  Reset index `i` to 0
      i<1                     //  Loop (1) as long as `i` is 0 (the first iteration),
      |!a.equals(t);          //  or the input array is not equal to the copy
      System.out.println(t))  //    After every iteration: print the modified List
    for(x.reverse(t),         //   Reverse the copied List
        i=0;                  //   Reset `i` to 0
        i<n;                  //   Inner loop (2) over the List
        i++)                  //     After every iteration: increase `i` by 1 again
      if(i<n-1)               //    Unless it's the last item in the List:
        x.swap(t,i,++i);      //     Swap the items at indexes `i` and `i+1` 
                              //     (by increasing `i` by 1 first with `++i`)
                              //   End of inner loop (2) (implicit / single-line body)
                              //  End of loop (1) (implicit / single-line body)
}                             // End of method
\$\endgroup\$
1
\$\begingroup\$

Java (OpenJDK 8), 257 245 243 226 206 205 bytes

n->{int i=0,k,t[]=new int[n];while(i<n)t[i]=++i;do{for(i=0;i<n/2;t[i]=t[n+~i],t[n+~i++]=k)k=t[i];for(k=1;k<n;t[k]=t[--k],t[k]=i,k+=3)i=t[k];System.out.println(java.util.Arrays.toString(t));}while(t[0]>1);}

Try it online!

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

MATL, 17 bytes

:`tP2ePXz!tG:-a]x

Try it online!

Explanation

:       % Implicit input: n. Push [1 2 ... n]
`       % Do...while
  t     %   Duplicate
  P     %   Reverse
  2e    %   Reshape into a 2-row matrix. A final 0 is added if needed
  P     %   Reverse each column
  Xz    %   Nonzero entries (i.e. remove final 0 if present). Gives a column vector
  !     %   Transpose into a row
  t     %   Duplicate
  G:    %   Push [1 2 ... n] again
  -     %   Subtract element-wise
  a     %   Any. Gives true if there is at least a nonzero value
]       % End. Go to next iteration if top of the stack is true.  So the loop ends
        % when [1 2 ... n] has been found again
x       % Delete top of the stack (which is [1 2  ... n]). Implicit display
\$\endgroup\$
1
\$\begingroup\$

Python 2, 165 159 138 81 bytes

x=input()+1
b=a=range(1,x)
while b:b=[b[x-min(x,i+1^1)]for i in a];print b;b*=a<b

Try it online!

-20 bytes thanks to @ChasBrown. (Sigh, I made a whole challenge about extended slicing syntax)

Whoa! GolfStorm (-57 bytes)! Thanks to Ian Gödel, tsh, and Jonathan Frech.

\$\endgroup\$
9
  • \$\begingroup\$ Instead of list(reversed(a)) try a[::-1]. \$\endgroup\$
    – Chas Brown
    Commented Sep 27, 2017 at 4:03
  • \$\begingroup\$ ' '*[2-(x<3),x][x%2] \$\endgroup\$
    – tsh
    Commented Sep 27, 2017 at 5:45
  • \$\begingroup\$ 132 bytes \$\endgroup\$
    – user74686
    Commented Sep 27, 2017 at 5:52
  • 1
    \$\begingroup\$ 88 bytes \$\endgroup\$
    – tsh
    Commented Sep 27, 2017 at 5:59
  • 1
    \$\begingroup\$ @tsh [b,0][b==a] -> b*(a!=b). \$\endgroup\$ Commented Sep 27, 2017 at 7:10
1
\$\begingroup\$

GolfScript, 33 bytes

Nope, I can't simplify the algorithm.

~),1>:a{-1%2/{-1%}%{+}*.p.a=!}do;

Try it online!

Explanation

~                                 # Dump the input
 ),                               # Generate inclusive range: 0 -> input
   1>:a                           # Set [1 2 ... input-1 input] to a without popping
       {                     }do  # Do ... While
                         .a=!     # The current item does not equal to a
        -1%                       # Reverse the item
           2/                     # Split into equal parts of 2
             {-1%}%               # For each equal part, reverse
                   {+}*           # Flatten the list
                       .p         # Print the list
                                ; # We don't need to implicit output the
                                  # extra value left on the stack
\$\endgroup\$
1
\$\begingroup\$

Vyxal 3 j, 8 bytes

ɾᶨλṚ2ẆVf

Try it Online!

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

JavaScript (ES6), 122 bytes

f=(n,a=[...Array(n)].map((_,i)=>i+1),r=[],b=a.map((_,i)=>a[n+~(i^1)]||a[0]))=>b.some((e,i)=>e>b[i+1],r.push(b))?f(n,b,r):r

r.push(a) could be used instead of r.push(b) to put the original permutation at the front.

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

Haskell, 97 bytes

This feels a bit long :(

f n|x<-[1..n]=x:takeWhile(/=x)(tail$iterate((r=<<).g.r)x)
r=reverse
g[]=[]
g x=take 2x:g(drop 2x)

Try it online!

Explanation/Ungolfed

-- starting with x, accumulate the results of repeatedly
-- applying the function permute
f n = x : takeWhile (/=x) (tail $ iterate permute x)
  where x = [1..n]
        -- reverse, cut2, reverse each pair & flatten
        permute = concatMap reverse . cut2 . reverse

-- recursively transform a list into groups of 2
cut2 [] = []
cut2 xs = take 2 xs : g (drop 2 xs)
\$\endgroup\$
0
\$\begingroup\$

Stacked, 42 bytes

[~>[rev 2#<$revflatmap]periodsteps behead]

Try it online!

Performs the given transformation using the periodsteps builtin. However, this builtin returns all of the elements, which includes the input's range as its first and last elements. We therefore behead the list, returning all but the first element.

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

AWK, 123 bytes

Not very tight, but this is the best I could come up with.

{for(N=$1;N>$i=++i;);for(;n++<(i%2?i:i>2?2:1);){for(k=0;k++<i;)K[k]=(z=i-k+(k-1)%2*2)?$z:$1;for(k=0;k++<N;){$k=K[k]}print}}

Try it online!

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

JavaScript, 136 bytes

(n)=>{for(a=[],i=0;i<n;a[i]=++i);for(j=0;j<(n&1?n:2);j++){a.reverse();for(i=0;i<a.length-1;i += 2)m=a[i],a[i]=a[i+1],a[i+1]=m;alert(a)}}
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -p, 89 bytes

$_=$;=join$",1..$_;do{$_=join$",reverse/\d+/g;s/(\d+) (\d+)/$2 $1/g;$\+=say}until$;eq$_}{

Try it online!

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

TypeScript’s type system, 203 193 190 183 bytes

//@ts-ignore
type F<N,A=[],E=A,O=N,G=[...N,...A]>=N extends[1,...infer D]?F<D,[N,...A]>:A extends[...infer R,infer X,infer Y]?F<[...N,X,Y],R,E,O>:E extends O[any]?O:F<[],G,E,[...O,G]>

Try it at the TS playground

I can’t believe I got this all to fit in a single type. This is definitely one of the coolest TS types submissions I’ve posted.

Edit: This explanation is really chaotic because this submission itself is chaotic; I don’t blame you if it makes zero sense to you

Explanation

The //@ts-ignore comment on the first line tells the compiler to suppress any warnings from the following line.

The beginning of the type describes its arguments:

type F<N,A=[],E=A,O=N,G=[...N,...A]>

What the arguments do is explained later, but you should know that G is an alias for N with A appended to it; it comes in handy later.

The type has three “stages”, which are entered at different times in the evaluation of the type.

  • The first stage converts the unary number to the range of unary numbers between 1 and the input. (At this stage, the input is in N, and A is the empty tuple.)

    N extends[1,...infer D]
    

    Is the first item of N a one? If so, remove it and call the rest D, and…

    F<D,[N,...A]>
    

    …recurse, with N set to D, and with N prepended to A.

    By the end of stage 1, A will contain the range from 1 to the input, E will be set equal to A, and N and O will both be the empty tuple.

    (E is the initial step; this will be how the type knows to terminate. O will be the list of intermediate results, which will be the final return value.)

  • If the first stage was not entered, because N is either empty or contains elements that aren’t ones, then the second stage is entered, to reverse and reorder the elements of A.

    A extends[...infer R,infer X,infer Y]
    

    If A has two or more items, call the last two X and Y respectively, and the rest R.

    F<[...N,X,Y],R,E,O>
    

    Recurse, appending X and Y to N, setting A to R, and keeping the values of E and O as they already are.

    By the end of this stage, N will contain the reversed and reordered items of A. A will be empty if it originally had an even number of items, but if its length was odd then it will contain the last item to be appended to N. This is a minor pain point of the solution, adding 14 bytes to alias G to N with A appended.

  • The third stage does the “repeat” step.

    E extends O[any]?O
    

    If E (the initial result) is contained in O (the list of intermediate results), then the program is finished; return O.

    F<[],G,E,[...O,G]>
    

    Otherwise, recurse with N set to the empty tuple (skipping stage 1 and going straight to stage 2), A set to G (the alias for N with A appended), E left unchanged, and O with G appended.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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