Фаро перемешать массив

31

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]  
DJMcMayhem
источник
Может ли массив содержать ноль элементов?
Дрянная Монахиня
@LeakyNun Мы скажем нет, вам не нужно обрабатывать ноль элементов.
DJMcMayhem
Связанные
Питер Тейлор
1
Любая перестановка конечного множества, если она повторяется достаточно много раз, в конечном итоге вернется туда, откуда она началась; это не специально для Фаро.
Грег Мартин

Ответы:

10

05AB1E , 5 байтов

Код:

F2äø˜

Объяснение, ввод: N, array:

F      # Do the following N times
 2ä    # Split the array into 2 pieces
   ø   # Zip
    ˜  # Deep flatten

Использует кодировку CP-1252 . Попробуйте онлайн! ,

Аднан
источник
1
Блин, я был слишком медленным!
Джордж Гибсон
19

vim, 62 59 54

qrma50%mb:norm@q<cr>ggqOjdd'apjma'b@q<esc>0"qDJ<C-a>D@"i@r<esc>xxdd@"

Вау. Возможно, это самая хакерская вещь, которую я написал для PPCG, и это о чем-то говорит.

Ввод принимается как N в первой строке, за которой следуют элементы массива, каждый из которых находится в отдельной строке.

qr         first, we're going to record the contents of the @r macro. this is
             the macro which does the faro-shuffle operation.
  ma       set the mark 'a at the beginning of the file
  50%      move to the 50% point of the file (i.e. halfway down)
  mb       set another mark here
  :norm@q  evaluate the recursive macro @q. we'll get to what that does later,
             but the interesting part here is that it's :norm@q instead of @q.
             this is because a recursive macro terminates at the end of the
             file, which means when @q terminates, @r would also abort, which
             would make calling it with a count impossible. running @q under
             :norm prevents this.
  gg       move back to the top of the file for the next iteration
q          end recording
O          now we're inserting contents of the @q macro, the recursive part
             we can't record it directly because it's destructive
  j        move to line directly below mark 'b (which was just set before @q)
  dd       delete this line and bring it...
  'ap      up after mark 'a (which starts on line 1, bringing the N/2th line
             directly below line 1, aka line 2)
  jma      replace mark 'a one line below this so that the next time we call
             'ap, the line from the second half is interleaved with the lines
             from the first half
  'b       jump back to mark 'b (remember, 'b is the last line of the first
             half of the file, originally reached via 50%)
  @q       call ourselves, causing the macro to run until hitting EOF
0"qD       delete this into register "q
J          delete the empty line that remains
<C-a>      here's another interesting bit: we want to run @r N times. but 0@r
             means "go to column 0, and then run @r once." so we have to
             increment the input number...
D@"        and then *that* many times...
  i@r        insert @r...
xx         ... and finally, delete two characters, which is the extra @r from
             the increment
dd         delete the sequence of @rs into the "" register...
@"         and run it!

На самом деле, возможно, я нашел несколько ошибок vim при написании этого ответа:

  • запись макросов невозможна в других макросах (при установке их текста вручную, а не с помощью q) или в пределах :*maps.

  • :let @a='<C-v><cr>'<cr>i<C-r>a выводит две строки, а не одну, по какой-то непонятной причине.

Я мог бы исследовать это позже.

Спасибо Dr Green Eggs и Ham DJ за 3 байта!

Дверная ручка
источник
4
Это красиво и ужасно. Я, вероятно, не хватает терпения, чтобы сделать это в VIM. :PКроме того, вы можете снять 2 байта, выполнив "rckвместо vgg"rc, и вы можете снять еще 5, выполнив dw@"i@r<esc>вместоAA@R<C-v><esc><esc>0D@"
DJMcMayhem
@DrGreenEggsandHamDJ Не могу сделать это первым, потому что он также захватывает завершающий перевод строки, но вторая оптимизация работает. Благодарность!
Дверная ручка
7

Python 2, 59 байт

def f(n,L):exec"l=len(L)/2;L=(L+L[1:]*~-l)[::l];"*n;print L

Другой подход, немного дольше, чем другие ответы Python. Работает только для положительных четных чисел элементов.

например, для 1, [1,2,3,4,5,6,7,8], взять массив и добавить его len(L)/2-1копии минус первый элемент, например

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

Тогда возьмите каждый len(L)/2элемент.

[1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8]
 ^       ^       ^       ^       ^       ^       ^       ^
Sp3000
источник
6

Python, 68 57 байт

f=lambda n,x:n and f(n-1,sum(zip(x,x[len(x)/2:]),()))or x

Спасибо @ Sp3000 за отыгрывание 11 байтов!

Проверьте это на Ideone .

Деннис
источник
6

Haskell, 62 байта

0!a=a
n!a|s<-length a=(n-1)![a!!mod(div(s*i+i)2)s|i<-[0..s-1]]

Пусть s = 2 · t будет размером списка. Я -й элемент нового списка получается взятием введите описание изображения здесь-го элемента старого списка, нулевой индекс, по модулю s .

Доказательство: если i = 2 · k чётно, то

                                         введите описание изображения здесь

и если i = 2 · k + 1 нечетно, то

                        введите описание изображения здесь

Таким образом, значения, используемые для индексации: 0, t , 1, t + 1, 2, t + 2,…

Линн
источник
5

J - 12 байт

Наречие (!) Принимает число перемешиваний слева и массив перемешивания справа.

/:#/:@$0,#^:

У 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 !

   1 (/:#/:@$0,#^:) 1 2 3 4 5 6 7 8
1 5 2 6 3 7 4 8

   f =: /:#/:@$0,#^:

   2  f  1 2 3 4 5 6 7 8
1 3 5 7 2 4 6 8

   7  f  _23 _37 52 0 _6 _7 _8 89   NB. "negative 1" is spelled _1
_23 _6 _37 _7 52 _8 0 89

   1  f  0 0 0 0 1 1 1              NB. odd-length lists
0 1 0 1 0 1 0
algorithmshark
источник
5

Pyth - 8 7 байт

спас 1 байт благодаря @issacg

usCc2GE

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

Maltysen
источник
2
Хм ... должно быть что-то не так в ответе Желе, если Пиф побеждает Желе.
Утренняя монахиня
2
Поменяйте местами порядок ввода и удалите, Qчтобы сохранить байт. Должно быть что-то не так с ответом Pyth, если Jelly превосходит Pyth. :)
Исаак
@isaacg, черт возьми, я мог поклясться, что пробовал раньше. Почему это работает? не должно ли это зацепить значение по умолчанию для uNone и сделать фиксированную точку?
Малтысен
@ Maltysen Вы правы, я думаю, что это случилось только на одном тестовом примере, который я попробовал. Прости за это.
Исаак
@LeakyNun Благодаря @Dennis и @issacg , Pyth и Jelly теперь равны (7 байт). ; D
Кевин Круйссен
2

JavaScript (ES6), 61 51 байт

(n,a)=>[...a].map((e,i)=>a[(i<<n)%~-a.length||i]=e)

Изменяет входной массив на месте и возвращает копию исходного массива. Если это недопустимо, &&aможно добавить суффикс для возврата измененного массива. Работает только для небольших значений из- nза ограничений целочисленной арифметики JavaScript. 61 60-байтовая рекурсивная версия, которая работает с большими версиями n, на основе формулы @ Lynn:

f=(n,a,l=a.length)=>n?f(n-1,a.map((_,i)=>a[(i*-~l>>1)%l])):a
Нил
источник
2

MATL , 11 байт

w:"tn2/e!1e

Спасибо @Dennis за исправление

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

объяснение

w         % Take the two inputs N and A. Swap them
:         % Generate [1 2 ... N]
"         % Repeat N times
  tn2/    %   Duplicate A. Number of elements divided by 2
  e       %   Reshape to that number of rows
  !       %   Transpose
  1e      %   Reshape to one row
          % End (implicit)
          % Display (implicit)
Луис Мендо
источник
Зачем это wнужно?
Дэвид
@ Дэвид Это было исправление. Без этого при N = 0 цикл не вводится и второй вход не берется
Луис Мендо
Ах, это раздражает!
Дэвид
2

J, 22 19 17 байт

3 байта благодаря @Gareth .

2 байта благодаря @algorithmshark .

-:@#({.,@,.}.)]^:

использование

>> f =: -:@#({.,@,.}.)]^:
>> 2 f 1 2 3 4 5 6 7 8
<< 1 3 5 7 2 4 6 8

Где >>STDIN и <<STDOUT.

Предыдущая 22-байтовая версия:

({~[:,/@|:@i.2,-:@#)^:

использование

>> f =: ({~[:,/@|:@i.2,-:@#)^:
>> 2 f 1 2 3 4 5 6 7 8
<< 1 3 5 7 2 4 6 8

Где >>находится STDIN и<<STDOUT.

Дрянная Монахиня
источник
Из-за правил синтаксического анализа J , вы можете отбросить внешних паренов на 2 символа.
алгоритм игры
Альтернатива с использованием транспонированного индекса {~2,@|:@i.@,-:@#^:для 18 байтов .
миль
Другой вариант , который использует 17 байт также[:,@|:]]\~_2%~#^:
мили
@ Miles Я считаю, ,@|:@$~2,-:@#^:работает на 15 байтов
Иона
1

Mathematica 44 байта

С 4 байтами, сохраненными благодаря @miles.

Riffle@@TakeDrop[#,Length@#/2]&~Nest~##&

Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[list, nShuffles]разбивает список на два равных подсписка и перемешивает Riffleих.


 Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[Range@8, 1]

{1, 5, 2, 6, 3, 7, 4, 8}


Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[Range@100, 23]

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

DavidC
источник
Используя TakeDropмы можем найти решение, используя 40 байтов, а Riffle@@TakeDrop[#,Length@#/2]&~Nest~##&также принять последовательность, ##которая будет проанализирована в качестве дополнительных аргументов Nest.
миль
@miles. Очень хорошее использование TakeDrop. И лучше использовать ##для вставки последовательности.
DavidC
1

APL, 23 21 символ

({⊃,/⍵(↑,¨↓)⍨2÷⍨⍴⍵}⍣N)A

Без предположения (спасибо Денису) и на 1 символ короче

({{∊,⌿2(2÷⍨≢⍵)⍴⍵}⍣⎕)⎕

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

user2070206
источник
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 будет длиной массива

  • у двойной
  • если x больше или равно половине L, то приращение y
  • держать у в пределах массива

или как код: y=(2*x+x/(L/2))%L

Это предполагает, что индикаторы начинаются с 0. Вот код, поясненный далее:

int[] faroShuffle( int[] array, int numberOfShuffles ) {
    //repeat the faro shuffle n times
    for( int index, length=array.length, destination[]; 0<numberOfShuffles--; array=destination ) {
        //new array to copy over the elements
        destination=new int[length];
        //copy the elements into the new array
        for( index=0; index<length; index++ )
            destination[(2*index+2*index/length)%length]=array[index];
        //at the end of each loop, copy the reference to the new array and use it going forward
    }
    return array;
}  

см. 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 байт )
Кевин Круйссен,
1

Юлия, 45 42 байта

a\n=n>0?reshape(a,endof(a)÷2,2)'[:]\~-n:a

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

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

Мы (пере) определяем бинарный оператор \для этой задачи. Пусть a будет массивом, а n неотрицательным целым числом.

Если n положительно, мы перемешиваем массив. Это достигается путем преобразования его в матрицу длиной (а) ÷ 2 строки и два столбца. 'транспонирует полученную матрицу, создавая две строки, затем выравнивая результат с помощью [:]. Так как Юлия хранит матрицы в главном порядке столбцов, это чередует две строки.

После этого мы вызываем \рекурсивно с shuffled a и n - 1 ( ~-n) в качестве аргументов, таким образом выполняя дополнительные тасования. Как только n достигает 0 , мы возвращаем текущее значение a .

Деннис
источник
0

На самом деле, 15 байтов

`;l½≈@│t)HZ♂i`n

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

Объяснение:

`;l½≈@│t)HZ♂i`n
`            `n  do the following n times:
 ;l½≈              push half the length of the array
     @             swap
      │            duplicate entire stack
       t)H         last L//2 elements, first L//2 elements
          Z♂i      zip, flatten each element
Mego
источник
0

Пролог, 116 байт

a([],[[],[]]).
a([H,I|T],[[H|U],[I|V]]):-a(T,[U,V]).
f(X,0,X).
f(X,N,Y):-N>0,M is N-1,f(X,M,Z),a(Z,[A,B]),append(A,B,Y).

использование

?- f([1,2,3,4,5,6,7,8],2,X).
X = [1, 5, 2, 6, 3, 7, 4, 8] ;
false.
Дрянная Монахиня
источник