Во время работы с числами я нашел интересную перестановку, которую вы можете сгенерировать из списка чисел. Если вы будете повторять одну и ту же перестановку достаточно много раз, вы всегда окажетесь в исходном массиве. Давайте использовать следующий список:

[1, 2, 3, 4, 5]

В качестве примера

1. Обратный массив. Теперь наш массив

   [5, 4, 3, 2, 1]
   

2. Переупорядочить (поменять) каждую пару. В нашем списке 2 пары: [5, 4]и [3, 2]. К сожалению, мы не можем сгруппировать их 1в пару, поэтому оставим их в покое. После замены каждой пары новый массив:

   [4, 5, 2, 3, 1]
   

3. Повторите шаги 1 и 2, пока мы не вернемся к исходному массиву. Вот следующие 4 шага:

   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
   

   Если длина списка, n нечетная, всегда будет ровно n шагов, чтобы вернуться к исходному массиву. Если n четное, для возврата к исходному массиву всегда потребуется 2 шага, если только n не равно 2, и в этом случае потребуется 1 шаг (потому что реверс и свопинг - это одно и то же).

Ваша задача на сегодня (если вы решите принять ее) состоит в том, чтобы визуализировать этот набор шагов для списков произвольной длины. Вы должны написать программу или функцию, которая принимает одно положительное целое число n в качестве входных данных и выполняет этот набор шагов для списка [1, n]. Вы должны вывести каждый промежуточный шаг по пути, будь то печать каждого шага или возврат их всех в виде списка шагов. Я не очень требователен к формату вывода, если ясно, что вы генерируете каждый шаг. Это означает (например) любой из них:

• Вывод каждого шага в виде списка в STDOUT

• Возврат списка списков

• Возврат списка строковых представлений каждого шага

• Возврат / вывод матрицы

было бы приемлемо.

Вы также должны вывести исходный массив, независимо от того, идет ли он в конце или в начале. (технически оба верны)

Вам придется обработать крайний случай 2, сделав 1 шаг вместо 2 , поэтому убедитесь, что ваше решение работает с вводом 2 (а 1 - это еще один потенциальный крайний случай).

Как обычно, это код-гольф , поэтому применяются стандартные лазейки, и вы пытаетесь сделать свое решение короче, чем любой другой на выбранном вами языке (или даже попытаться обыграть другой язык, который обычно короче вашего, если вы чувствуете себя лучше) за вызов).

Тест 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]

И для хорошей меры, вот один гигантский контрольный пример:

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]

Удачи в гольф!

TI-Basic (серия 83), 58 57 54 байта (104 символа)

: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

объяснение

Принимает входные данные Ans(например, написать, 5:prgmNAMEчтобы использовать списки размера пять).

Создает три вспомогательных списка заданного размера (которые создаются заново ᶫBна каждом шаге): ᶫB = ᶫC = {1,2,3,4,5,...}и ᶫD = {-1,-1,-2,-2,-3,...}. На каждом шаге сортирует ᶫCи ᶫDв порядке убывания, применяя одну и ту же перестановку к ᶫA. В случае ᶫC, это меняет ᶫA, а в случае ᶫD, это меняет местами смежные пары, потому что TI-Basic использует действительно глупую реализацию сортировки выбора, для SortD(которой переупорядочивает столько идентичных элементов, сколько возможно. когдаᶫAᶫB снова становится равным , мы останавливаемся.

Нет, серьезно, их встроенный алгоритм сортировки - моя вторая по величине жалоба с интерпретатором TI-Basic. (Моя самая большая жалоба заключается в том, как много вложенных циклов замедляет работу интерпретатора, поскольку данные цикла хранятся в стеке, но стек выращен не с того конца, поэтому калькулятор должен перемещать весь стек каждый раз при нажатии элемента или выскочил.) Но на этот раз это удобно.

-1 байт: Pauseсохраняет значение, на которое печатается Ans, которое короче, чем ссылкаᶫA .

-3 байта: принять входные данные в Ans

Желе , 10 байт

RµUs2UFµÐĿ

Попробуйте онлайн!

объяснение

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

Заметка

Если исходный диапазон должен быть в конце, добавьте ṙ1к коду 12 байт.

05AB1E , 13 11 байт

LIGÂ2ôí˜})Ù

Попробуйте онлайн!

объяснение

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

JavaScript (ES6), 89 85

редактировать 4 байта, сохраненные thx @JustinMariner

Используя тот факт, что, когда любой элемент находится в нужном месте, все элементы.

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

Меньше гольфа

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

Тест

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

Mathematica, 142 байта

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

JavaScript (ES6), 79 байт

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

Выводит список для каждого шага.

Обратите внимание, что нам не нужно инициализировать массив, чтобы заставить шарик катиться. Если неинициализировано ( xне определено), мы можем использовать индексы массива (параметр i), чтобы сделать первый шаг:

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

Тестовые случаи:

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

R 109 95 94 79 74 62 байта

Если тот факт, что код выбрасывает предупреждения поверх фактического решения (без предупреждений, если n1, 3 предупреждения, если nчетное, и nпредупреждений, если nнечетный), не является проблемой, то следующее работает аналогично предыдущему решению, благодаря vector переработка:

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

Попробуйте онлайн!

Еще раз спасибо @Giuseppe за дополнительные 12 байтов!

Предыдущее решение без предупреждения на 94 байтах:

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

Попробуйте онлайн!

Исходное решение на 109 байт :

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}

Попробуйте онлайн!

Japt , 20 18 15 12 байт

õ
£=ò2n)ÔcÃâ

Попробуйте ( -Rпометьте только для визуализации)

1 байт сохранен благодаря 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

Шелуха , 9 байт

U¡ȯṁ↔C2↔ḣ

Попробуйте онлайн!

            -- 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]

Рубин , 64 57 52 50 байт

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

Попробуйте онлайн!

Как это работает:

Сначала создайте диапазон, затем повторите перестановку x раз: используйте отрицательный индекс, но переверните последний бит, чтобы мы получили последовательность -2, -1, -4, -3 ... если x четное, это закончится хорошо, если нет, мы добавим оставшийся элемент в конце. Последний шаг: отфильтровываем повторяющиеся массивы (поэтому мы охватываем все случаи: x = 1, x = 2, нечетные и четные числа)

Haskell, 75 74 байта

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]

Попробуйте онлайн!

gвыполняет парные свопы, hодин шаг (реверс + переупорядочение), !многократно применяется h(и собирает промежуточные результаты), пока заказ не будет восстановлен. Примечание: !принимает дополнительный, но неиспользуемый дополнительный параметр 0только для того, чтобы сделать его инфиксным оператором. Основная функция pзапускает его.

Редактировать: Спасибо @Angs за байт.

Ява 8, 215 214 байт

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

Я попытался сыграть в гольф с использованием реальных массивов вместо списка, но как реверсирование, так и свопинг будут занимать слишком много байтов. Может быть, это можно объединить в один цикл (вместо сперва реверсирования, а затем свопинга), но мне еще предстоит выяснить это.
Это, безусловно, можно играть в гольф еще немного, хотя.

Объяснение:

Попробуй это здесь.

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

Java (OpenJDK 8) , 257 245 243 226 206 205 байт

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

Попробуйте онлайн!

MATL , 17 байт

:`tP2ePXz!tG:-a]x

Попробуйте онлайн!

объяснение

:       % 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

Stax , 17 байт

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

Запустите и отладьте его

объяснение

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

Удивил, что он работает так же быстро, как и тестировал до 399, прежде чем я больше не хотел настраивать свой браузер.

JavaScript (ES6), 122 байта

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)может быть использован вместо того, r.push(b)чтобы поставить исходную перестановку впереди.

Haskell , 97 байт

Это чувствует себя немного долго :(

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

Попробуйте онлайн!

Объяснение / 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)

С накоплением , 42 байта

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

Попробуйте онлайн!

Выполняет данное преобразование с помощью periodstepsвстроенного. Однако эта встроенная функция возвращает все элементы, включая диапазон ввода в качестве первого и последнего элементов. Поэтому мы обезглавливаем список, возвращая все, кроме первого элемента.

AWK , 123 байта

Не очень туго, но это лучшее, что я мог придумать.

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

Попробуйте онлайн!

Python 2 , 165 159 138 81 байт

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

Попробуйте онлайн!

-20 байт благодаря @ChasBrown . (Вздох, я сделал целый вызов по поводу расширенного синтаксиса срезов)

Вау! GolfStorm (-57 байт)! Спасибо Яну Гёделю, Тшу и Джонатану Фреху.

JavaScript, 136 байт

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