Faro перетасовать является метод часто используется магами «Перемешать» колода. Для выполнения перетасовки Фаро вы сначала разрезаете колоду на 2 равные половины, а затем чередуете две половины. Например
[1 2 3 4 5 6 7 8]
Фаро перетасовал
[1 5 2 6 3 7 4 8]
Это может быть повторено любое количество раз. Интересно, что если вы повторите это достаточно много раз, вы всегда окажетесь в исходном массиве. Например:
[1 2 3 4 5 6 7 8]
[1 5 2 6 3 7 4 8]
[1 3 5 7 2 4 6 8]
[1 2 3 4 5 6 7 8]
Обратите внимание, что 1 остается внизу, а 8 - сверху. Это делает это внешним перемешиванием . Это важное различие.
Соревнование
Учитывая массив целых чисел A и число N , выведите массив после N Faro shuffles. A может содержать повторяющиеся или отрицательные элементы, но всегда будет иметь четное количество элементов. Вы можете предположить, что массив не будет пустым. Вы также можете предположить, что N будет неотрицательным целым числом, хотя оно может быть и 0. Вы можете использовать эти входные данные любым разумным способом. Самый короткий ответ в байтах побеждает!
Тест IO:
#N, A, Output
1, [1, 2, 3, 4, 5, 6, 7, 8] [1, 5, 2, 6, 3, 7, 4, 8]
2, [1, 2, 3, 4, 5, 6, 7, 8] [1, 3, 5, 7, 2, 4, 6, 8]
7, [-23, -37, 52, 0, -6, -7, -8, 89] [-23, -6, -37, -7, 52, -8, 0, 89]
0, [4, 8, 15, 16, 23, 42] [4, 8, 15, 16, 23, 42]
11, [10, 11, 8, 15, 13, 13, 19, 3, 7, 3, 15, 19] [10, 19, 11, 3, 8, 7, 15, 3, 13, 15, 13, 19]
И массивный контрольный пример:
23, [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, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
Должен вывести:
[1, 30, 59, 88, 18, 47, 76, 6, 35, 64, 93, 23, 52, 81, 11, 40, 69, 98, 28, 57, 86, 16, 45, 74, 4, 33, 62, 91, 21, 50, 79, 9, 38, 67, 96, 26, 55, 84, 14, 43, 72, 2, 31, 60, 89, 19, 48, 77, 7, 36, 65, 94, 24, 53, 82, 12, 41, 70, 99, 29, 58, 87, 17, 46, 75, 5, 34, 63, 92, 22, 51, 80, 10, 39, 68, 97, 27, 56, 85, 15, 44, 73, 3, 32, 61, 90, 20, 49, 78, 8, 37, 66, 95, 25, 54, 83, 13, 42, 71, 100]
источник
Ответы:
05AB1E , 5 байтов
Код:
Объяснение, ввод:
N
,array
:Использует кодировку CP-1252 . Попробуйте онлайн! ,
источник
vim,
625954Вау. Возможно, это самая хакерская вещь, которую я написал для PPCG, и это о чем-то говорит.
Ввод принимается как N в первой строке, за которой следуют элементы массива, каждый из которых находится в отдельной строке.
На самом деле, возможно, я нашел несколько ошибок vim при написании этого ответа:
запись макросов невозможна в других макросах (при установке их текста вручную, а не с помощью
q
) или в пределах:*map
s.:let @a='<C-v><cr>'<cr>i<C-r>a
выводит две строки, а не одну, по какой-то непонятной причине.Я мог бы исследовать это позже.
Спасибо Dr Green Eggs и Ham DJ за 3 байта!
источник
:P
Кроме того, вы можете снять 2 байта, выполнив"rck
вместоvgg"rc
, и вы можете снять еще 5, выполнивdw@"i@r<esc>
вместоAA@R<C-v><esc><esc>0D@"
Python 2, 59 байт
Другой подход, немного дольше, чем другие ответы Python. Работает только для положительных четных чисел элементов.
например, для
1, [1,2,3,4,5,6,7,8]
, взять массив и добавить егоlen(L)/2-1
копии минус первый элемент, напримерТогда возьмите каждый
len(L)/2
элемент.источник
Python,
6857 байтСпасибо @ Sp3000 за отыгрывание 11 байтов!
Проверьте это на Ideone .
источник
Haskell, 62 байта
Пусть s = 2 · t будет размером списка. Я -й элемент нового списка получается взятием -го элемента старого списка, нулевой индекс, по модулю s .
Доказательство: если i = 2 · k чётно, то
и если i = 2 · k + 1 нечетно, то
Таким образом, значения, используемые для индексации: 0, t , 1, t + 1, 2, t + 2,…
источник
J - 12 байт
Наречие (!) Принимает число перемешиваний слева и массив перемешивания справа.
У J-парсера есть правила написания молчаливых наречий , но они имеют очень низкий приоритет: если вы хотите использовать последовательность глаголов в качестве левого аргумента, вы можете опустить необходимый набор скобок. Таким образом, вышесказанное на самом деле является сокращением
(/:#/:@$0,#)^:
, которое принимает число перемешиваний слева как наречие, а затем становится монадической функцией, переводящей массив в перемешивание справа.Тем не менее, мы тасуем следующим образом.
#
это длина массива, поэтому0,#
список из двух элементов: 0, за которым следует что-то ненулевое. Затем#/:@$
реплицирует это в список до входного массива и принимает вектор его сортировки .Вектор сортировки списка - это информация о том, как сортировать список: индекс (на основе 0) наименьшего элемента, за которым следует индекс следующего наименьшего, и так далее. Например, вектор сортировки
0 1 0 1 ...
будет таким0 2 4 ... 1 3 5 ...
.Если бы J теперь сортировал этот вектор сортировки, Фару бы это перемешал; но это было бы тривиально, так как мы
0 1 2 3 ...
вернемся. Таким образом, мы используем dyadic/:
для сортировки входного массива, как если бы он был0 2 4 ... 1 3 5 ...
, что Фаро перемешивает.Пример использования ниже. Попробуйте сами на tryj.tk !
источник
Pyth -
87 байтспас 1 байт благодаря @issacg
Попробуйте это онлайн здесь .
источник
Q
чтобы сохранить байт. Должно быть что-то не так с ответом Pyth, если Jelly превосходит Pyth. :)u
None и сделать фиксированную точку?Желе,
97 байт2 байта благодаря Денису!
Попробуйте онлайн!
объяснение
Предыдущая 9-байтовая версия:
Попробуйте онлайн!
источник
JavaScript (ES6),
6151 байтИзменяет входной массив на месте и возвращает копию исходного массива. Если это недопустимо,
&&a
можно добавить суффикс для возврата измененного массива. Работает только для небольших значений из-n
за ограничений целочисленной арифметики JavaScript.6160-байтовая рекурсивная версия, которая работает с большими версиямиn
, на основе формулы @ Lynn:источник
MATL , 11 байт
Спасибо @Dennis за исправление
Попробуйте онлайн!
объяснение
источник
w
нужно?J,
221917 байт3 байта благодаря @Gareth .
2 байта благодаря @algorithmshark .
использование
Где
>>
STDIN и<<
STDOUT.Предыдущая 22-байтовая версия:
использование
Где
>>
находится STDIN и<<
STDOUT.источник
{~2,@|:@i.@,-:@#^:
для 18 байтов .[:,@|:]]\~_2%~#^:
,@|:@$~2,-:@#^:
работает на 15 байтовMathematica 44 байта
С 4 байтами, сохраненными благодаря @miles.
Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[list, nShuffles]
разбивает список на два равных подсписка и перемешиваетRiffle
их.{1, 5, 2, 6, 3, 7, 4, 8}
{1, 30, 59, 88, 18, 47, 76, 6, 35, 64, 93, 23, 52, 81, 11, 40, 69, 98, 28, 57, 86, 16, 45, 74, 4 , 33, 62, 91, 21, 50, 79, 9, 38, 67, 96, 26, 55, 84, 14, 43, 72, 2, 31, 60, 89, 19, 48, 77, 7, 36 , 65, 94, 24, 53, 82, 12, 41, 70, 99, 29, 58, 87, 17, 46, 75, 5, 34, 63, 92, 22, 51, 80, 10, 39, 68 , 97, 27, 56, 85, 15, 44, 73, 3, 32, 61, 90, 20, 49, 78, 8, 37, 66, 95, 25, 54, 83, 13, 42, 71, 100 }
источник
TakeDrop
мы можем найти решение, используя 40 байтов, аRiffle@@TakeDrop[#,Length@#/2]&~Nest~##&
также принять последовательность,##
которая будет проанализирована в качестве дополнительных аргументовNest
.TakeDrop
. И лучше использовать##
для вставки последовательности.APL,
2321 символБез предположения (спасибо Денису) и на 1 символ короче
Попробуйте это онлайн .
источник
java, 109 байт
int[]f(int[]a,int n){for(int x,q=a.length,d[];0<n--;a=d){d=new int[q];for(x=0;x<q;x++)d[(2*x+2*x/q)%q]=a[x];}return a;}
Объяснение: Существует схема того, как элементы перемещаются, когда они перетасовываются:
пусть х будет исходным индексом
пусть у будет новый индекс
пусть L будет длиной массива
или как код:
y=(2*x+x/(L/2))%L
Это предполагает, что индикаторы начинаются с 0. Вот код, поясненный далее:
см. ideone для тестовых случаев
источник
void f(int[]a,int n){for(int x,q=a.length,d[];0<n--;a=d)for(d=new int[q],x=0;x<q;)d[(2*x+2*x/q)%q]=a[x++];}
( 107 байт - ваш текущий ответ 119, а не 109, так что -12 байт). Так как вы изменяете входной массив, нет необходимости возвращать его, поэтому вы можете изменить его на void, чтобы уменьшить байты. Да, и если вы преобразуете в лямбду Java 8 с карри, вы можете сделать ее еще короче:a->n->{for(int x,q=a.length,d[];0<n--;a=d){d=new int[q];for(x=0;x<q;x++)d[(2*x+2*x/q)%q]=a[x];}}
( 96 байт )Юлия,
4542 байтаПопробуйте онлайн!
Как это работает
Мы (пере) определяем бинарный оператор
\
для этой задачи. Пусть a будет массивом, а n неотрицательным целым числом.Если n положительно, мы перемешиваем массив. Это достигается путем преобразования его в матрицу длиной (а) ÷ 2 строки и два столбца.
'
транспонирует полученную матрицу, создавая две строки, затем выравнивая результат с помощью[:]
. Так как Юлия хранит матрицы в главном порядке столбцов, это чередует две строки.После этого мы вызываем
\
рекурсивно с shuffled a и n - 1 (~-n
) в качестве аргументов, таким образом выполняя дополнительные тасования. Как только n достигает 0 , мы возвращаем текущее значение a .источник
Пайк, 7 байт
Попробуй это здесь!
источник
На самом деле, 15 байтов
Попробуйте онлайн!
Объяснение:
источник
Пролог, 116 байт
использование
источник
Perl 5
-lan
, 52 байтаПопробуйте онлайн!
источник
PHP, 98 байт
Попробуйте онлайн .
источник