Как компьютерные ученые, вы, вероятно, все знакомы с основными операциями со списком pop и push . Это простые операции, которые изменяют список элементов. Тем не менее, вы когда-нибудь слышали об операционном флопе ? (как в flip- флоп )? Это довольно просто. Если задано число n , поменяйте местами первые n элементов списка. Вот пример:

>>> a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> a.flop(4)
[4, 3, 2, 1, 5, 6, 7, 8, 9, 10]

Крутая вещь в операции флопа состоит в том, что вы можете использовать ее для создания некоторых интересных вещей в списке, таких как сортировка . Мы собираемся сделать что-то подобное с флопами:

Дан список целых чисел «Сосед это». Другими словами, сортируйте его так, чтобы каждый повторяющийся элемент появлялся последовательно.

Это можно сделать с помощью флопов! Например, возьмите следующий список:

>>> a = [3, 2, 1, 4, 3, 3, 2]
>>> a.flop(4)
[4, 1, 2, 3, 3, 3, 2]
>>> a.flop(3)
[2, 1, 4, 3, 3, 3, 2]
>>> a.flop(6)
[3, 3, 3, 4, 1, 2, 2]

Это приводит нас к определению сегодняшнего вызова:

Имея список целых чисел, выведите любой набор флопов, который приведет к соседству списка.

Используя последний список в качестве примера, вы должны вывести:

4
3
6

потому что смещение списка на 4, затем на 3, затем на 6 приведет к соседнему списку. Имейте в виду, что вам не нужно печатать кратчайший список флопов, который соседствует со списком. Если вы напечатали:

4
4
4
3
1
1
6
2
2

вместо этого это все равно будет действительный вывод. Однако вы можете никогда не вывести число, превышающее длину списка. Это потому, что для списка a = [1, 2, 3]вызов не a.flop(4)имеет смысла.

Вот некоторые примеры:

#Input:
[2, 6, 0, 3, 1, 5, 5, 0, 5, 1]

#Output
[3, 7, 8, 6, 9]


#Input
[1, 2]

#Output
<any list of integers under 3, including an empty list>


#Input
[2, 6, 0, 2, 1, 4, 5, 1, 3, 2, 1, 5, 6, 4, 4, 1, 4, 6, 6, 0]

#Output
[3, 19, 17, 7, 2, 4, 11, 15, 2, 7, 13, 4, 14, 2]


#Input
[1, 1, 1, 1, 2, 2, 2, -1, 4]

#Output
[]


#Input
[4, 4, 8, 8, 15, 16, 16, 23, 23, 42, 42, 15]

#Output
[12, 7]

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

Вы можете принимать и выводить данные в любом разумном формате. Например, аргументы функции / возвращаемое значение, STDIN / STDOUT, чтение / запись файла и т. Д. Являются действительными. Как обычно, это код-гольф , так что составьте самую короткую программу, какую только сможете, и получайте удовольствие! :)

Haskell , 98 71 байт

h.r
h(x:s)|(a,b)<-span(/=x)s=l b:l s:h(b++r a)
h e=e
r=reverse
l=length

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

объяснение

Для списка длины nэтот метод производит 2*nпровалы. Он работает, просматривая последний элемент списка, ища тот же элемент в списке и переворачивая его со второй на последнюю позицию. Затем список с последним удаленным элементом рекурсивно «соседствует».

Для списка [1,2,3,1,2]алгоритм работает так:

[1,2,3,1,2]  flip longest prefix that ends in 2: flop 2
[2,1,3,1,2]  bring first element to second to last position: flop n-1 = flop 4
[1,3,1,2,2]  recursively work on n-1 list
[1,3,1,2]    there is no other 2: flop 0
[1,3,1,2]    flop n-1 = flop 3
[1,3,1,2]    recurse
[1,3,1]      flop 1
[1,3,1]      flop 2
[3,1,1]      recurse
[3,1]        flop 0
[3,1]        flop 1
 ...

Все вместе это приводит к флопам [2,4,0,3,1,2,0,1,0,0]и соседнему списку [3,1,1,2,2].

Wolfram Language (Mathematica) , 71 байт

If[(n=Tr[1^#])<1,{},{i=Last@Ordering@#,n,n-1,i-1}~Join~#0[#~Drop~{i}]]&

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

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

Учитывая массив длины n, выводит последовательность 4nфлопов, которые сортируют массив в порядке возрастания: в частности, помещая дубликаты элементов рядом друг с другом.

Идея состоит в том, что для сортировки массива мы перемещаем его самый большой элемент в конец, а затем сортируем первые n-1элементы массива. Чтобы избежать реализации операции флопа, мы перемещаем самый большой элемент в конец таким образом, чтобы не мешать другим элементам:

{3, 2, 1, 5, 3, 3, 2}    starting array, with largest element in position 4
{5, 1, 2, 3, 3, 3, 2}    flop 4 to put the largest element at the beginning
{2, 3, 3, 3, 2, 1, 5}    flop 7 to put the largest element at the end
{1, 2, 3, 3, 3, 2, 5}    flop 6 (7-1) to reverse the effect of flop 7 on other elements
{3, 2, 1, 3, 3, 2, 5}    flop 3 (4-1) to reverse the effect of flop 4 on other elements

В общем, если самый большой элемент находится в позиции i, последовательность флопов, которая перемещает его в конец, такова i, n, n-1, i-1.

Python 2 , 69 байт

l=input()
while l:k=l.index(max(l));print-~k,len(l),;l=l[:k:-1]+l[:k]

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

Желе , 19 17 байт

ỤỤạ‘Ḣ
ỤÇÐƤĖµUż’ṚF

Сортирует список.

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

Чисто , 88 байт

Я думаю, что есть, возможно, короче с охранниками, но я еще не нашел его.

import StdEnv
$[h:t]#(a,b)=span((<>)h)t
=map length[b,t]++ $(b++r a)
$e=e
r=reverse

$o r

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

Как функция буквальная. Работает так же, как ответ Хаскелла Лайкони , но играет в гольф немного по-другому, и, конечно, на другом языке.

JavaScript, 150 байт

(a,f=n=>(a=[...a.slice(0, n).reverse(),...a.slice(n)],n),l=a.length,i=0)=>a.reduce(c=>[...c,f(a.indexOf(Math.max(...a.slice(0, l-i)))+1),f(l-i++)],[])

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

JavaScript, 151 байт

a=>{f=n=>(a=[...a.slice(0,n).reverse(),...a.slice(n)],n),r=[];for(i=a.length+1;--i>0;)r.push(f(a.indexOf(Math.max(...a.slice(0, i)))+1),f(i));return r}

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

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

Ungolfed:

array => {
  let flop = n => {
    array = [...array.slice(0, n).reverse(), ...array.slice(n)]; 
    return n;
  }
  let flops = [];
  for (let i = array.length + 1; --i > 0;) 
  {
    let maxIndex = array.indexOf(Math.max(...array.slice(0, i)));
    flops.push(flop(maxIndex + 1), flop(i));
  }
  return flops;
}

Perl 5.10 (или выше), 66 байт

Включает +3в довести язык до уровня Perl 5,10 считается свободным-nuse 5.10.0

#!/usr/bin/perl -n
use 5.10.0;
$'>=$&or$.=s/(\S+) \G(\S+)/$2 $1/*say"$. 2 $."while$.++,/\S+ /g

Запустите с вводом одной строкой на STDIN:

flop.pl <<< "1 8 3 -5 6"

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

На этот раз было удивительно трудно попасть в тот же стадион, что и в питоне :-)

C (gcc) , 165 160 байт

• Благодаря Celercat для экономии пяти байтов.

m,j,t;f(A,l)int*A;{for(j=0;j+j<l;A[j]=A[l+~j],A[l+~j++]=t)t=A[j];}F(A,l)int*A;{for(;l;f(A,++m),printf("%d,%d,",m,l),f(A,l--))for(j=m=0;j<l;j++)m=A[j]>A[m]?j:m;}

• Попробуйте онлайн!
• верификация