The Three 'R's: Reverse, Reorder, Repeat

Question

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 code-golf, 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!

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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()'>

Answer 5

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!

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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)

Answer 10

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]

Answer 11

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.

Answer 12

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

Answer 13

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!

Answer 14

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

Answer 15

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.

Answer 16

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

Answer 17

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.

Answer 18

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.

Answer 19

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)

Answer 20

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.

Answer 21

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!

Answer 22

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