Случайный гольф дня № 1: перемешать массив

35

О серии

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

Тем не менее, я буду поддерживать таблицу лидеров по всем задачам. Сериал будет проходить более 9 задач (пока), один раз в несколько дней. Каждый пользователь, участвующий во всех 9 соревнованиях, имеет право на победу во всей серии. Их общий балл - это сумма их самых коротких заявок на каждый вызов (поэтому, если вы ответите на вызов дважды, к баллу будет засчитан только лучший ответ). Если кто-то займет первое место в этом общем списке лидеров в течение 28 дней, я назначу ему награду в 500 представителей .

Несмотря на то, что у меня есть ряд идей для этой серии, будущие проблемы еще не заложены. Если у вас есть какие-либо предложения, пожалуйста, сообщите мне об этом в соответствующей песочнице .

Отверстие 1: перемешать массив

Первая задача довольно проста: при наличии непустого массива целых чисел перемешать его случайным образом. Есть несколько правил:

  • Каждая возможная перестановка должна быть возвращена с одинаковой вероятностью (поэтому перемешивание должно иметь равномерное распределение). Вы можете проверить, является ли ваш алгоритм единообразным / беспристрастным, реализовав его в JavaScript на Will it Shuffle , который будет генерировать матрицу смещений - результат должен выглядеть так же равномерно, как и встроенные значения Fisher-Yates или sort (в произвольном порядке) .
  • Вы не должны использовать какой-либо встроенный или сторонний метод для перемешивания массива или генерации случайной перестановки (или перечисления всех перестановок). В частности, единственная встроенная случайная функция, которую вы можете использовать, - это получение одного случайного числа за раз . Вы можете предположить, что любой встроенный метод случайных чисел работает в O (1) и является абсолютно равномерным в течение запрошенного интервала (в математическом смысле - вы можете игнорировать детали представления с плавающей точкой здесь). Если ваш язык позволяет вам получить список из m случайных чисел одновременно, вы можете использовать эту возможность при условии, что m номеров не зависят друг от друга, и вы считаете это как O (m).
  • Ваша реализация не должна превышать временную сложность O (N) , где N - размер массива, который должен быть перетасован. Например, вы не можете "сортировать по случайным числам".
  • Вы можете либо перемешать массив на месте, либо создать новый массив (в этом случае старый массив может быть изменен по вашему усмотрению).

Вы можете написать полную программу или функцию и получать ввод через STDIN, аргумент командной строки, аргумент функции или приглашение и производить вывод через возвращаемое значение или печатать в STDOUT (или ближайшую альтернативу). Если вы пишете функцию, которая перемешивает массив на месте, вам, конечно, не нужно возвращать его (при условии, что ваш язык позволяет вам получить доступ к измененному массиву после возврата из функции).

Вход и выход могут быть в любом удобном формате списка или строки, но должны поддерживать произвольные целые числа в диапазоне -2 31 ≤ x <2 31 . В принципе, ваш код должен работать для массивов длиной до 2 31 , хотя это не обязательно должно умещаться в вашей памяти или завершаться в течение разумного периода времени. (Я просто не хочу видеть произвольные ограничения размера для циклов жесткого кода или чего-то еще.)

Это код гольф, поэтому выигрывает самое короткое представление (в байтах).

Leaderboard

Следующий фрагмент создаст таблицу лидеров по всем задачам серии.

Чтобы убедиться, что ваши ответы отображаются, начните каждый ответ с заголовка, используя следующий шаблон уценки:

# Language Name, N bytes

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

# Ruby, <s>104</s> <s>101</s> 96 bytes

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

Мартин Эндер
источник
7
Я разочарован тем, что мы не можем быть «умными» и использовать библиотечные функции, отличные от «получить случайное число» . Мы хотим посмотреть еще на 69 реализаций тасования Фишера-Йейтса? Пожалуйста, рассмотрите возможность удаления этого правила в будущих задачах. Кроме того, почему ограничение по времени сложности? Пожалуйста, подумайте о том, чтобы уменьшить его хотя бы до O (n ^ 2); Я также думаю, что кто-то может найти особенно удачную реализацию, если вы позволите O (n!).
Анатолий
7
@anatolyg Снятие ограничений сводится к тому, что каждый ответ либо sortby(random)(причина ограничения по времени), либо просто .shuffle()(причина ограничения встроенных функций), что, на мой взгляд, гораздо менее разумно, чем реализация Фишера-Йейтса или какой-то другой подходить.
Мартин Эндер
1
Если тасуется на месте, должна ли функция возвращать массив или достаточно, чтобы он был изменен? Могу ли я написать функцию shuffle(array)вместо newArray=shuffle(array)?
Geobits
1
@Bakuriu Утверждение, что вы можете сортировать в линейном времени, если числа фиксированы, немного похоже на утверждение, что вы можете сделать что-нибудь в O (1), если размеры ввода фиксированы. Также соответствующим ограничением являются массивы фиксированного размера, а не целые числа фиксированного размера - потому что размер массива определяет, насколько большими должны быть ваши случайные числа. В любом случае, ограничение по сложности времени, конечно же, относится к общему алгоритму, который вы реализуете, тогда как ограничения по размеру входных данных существуют, поэтому вам не нужно использовать целые числа произвольной точности, если ваш язык не использует их из коробки. ,
Мартин Эндер
2
Почему решение Адама имеет размер 43319 байт, а на самом деле это 14?
boboquack

Ответы:

20

Дьялог АПЛ, 25 24 байта

Сначала для 25-символьного решения: i{⊃a[⍺⍵]←a[⍵⍺]}¨?i←⌽⍳⍴a←⎕

                      a←⎕ ⍝ evaluated input, assign to "a"
                     ⍴a   ⍝ length
                    ⍳⍴a   ⍝ 1 2 .. length
                   ⌽⍳⍴a   ⍝ length .. 2 1
                 i←       ⍝ assign to "i"
                ?i        ⍝ random choices: (1..length)(1..length-1)..(1 2)(1)
i{            }¨?i        ⍝ for each index ⍺ and corresponding random choice ⍵
   a[⍺⍵]←a[⍵⍺]            ⍝ swap a[⍺] and a[⍵]
        ←                 ⍝ in Dyalog, assignment returns its right-hand side
  ⊃                       ⍝ first element, i.e. a[⍵]
                          ⍝ the result from {} is an array of all those a[⍵]

После некоторых преобразований эквивалентности выше:

i {}¨ ?i  ←→  i {}¨∘? i   ⍝ because A f∘g B ←→ A f g B
          ←→  {}¨∘?⍨ i    ⍝ because f⍨ B ←→ B f B

мы можем избавиться от задания i←и сохранить персонажа:

{⊃a[⍺⍵]←a[⍵⍺]}¨∘?⍨⌽⍳⍴a←⎕

СПП
источник
3
... разум. перегорел.
danwyand
1
язык я должен читать справа налево ?? Вот Это Да!
Светящийся
5
@ Светящийся, как это часто бывает с математическими обозначениями: sin cos ln sqrt x
ngn
4
@ngn, когда вы так говорите, мой предыдущий комментарий выглядит смешным. га.
Световой
5
@ronalchn Есть 8-битные кодировки для APL, как эта или эта другая; Я слышал, что Dyalog использует один из них, как альтернативу Unicode.
Анатолий
12

80386 машинный код, 44 24 байта

Hexdump кода:

60 8b fa 0f c7 f0 33 d2 f7 f1 49 8b 04 8f 87 04
97 89 04 8f 75 ed 61 c3

Спасибо FUZxxl, который предложил использовать rdrandинструкцию.

Вот исходный код (может быть скомпилирован Visual Studio):

__declspec(naked) void __fastcall shuffle(unsigned size, int array[])
{
    // fastcall convention:
    // ecx = size
    // edx = array
    _asm
    {
        pushad;             // save registers
        mov edi, edx;       // edi now points to the array

    myloop:
        rdrand eax;         // get a random number
        xor edx, edx;
        div ecx;            // edx = random index in the array

        dec ecx;            // count down
        mov eax, [edi + 4 * ecx];   // swap elements
        xchg eax, [edi + 4 * edx];  // swap elements
        mov [edi + 4 * ecx], eax;   // swap elements
        jnz myloop;

        popad;              // restore registers
        ret;
    }
}

Еще одна реализация Фишера-Йейтса. Большая часть игры в гольф была достигнута путем передачи параметров в регистрах.

anatolyg
источник
1
Вы могли бы также использовать rdrandдля дерьма и хихиканья.
FUZxxl
@FUZxxl Я полностью забыл об этом! Жаль, что удаляет самую интересную часть моего ответа ...
Анатолий
9

Ява, 88 101

Основной трюк Фишера-Йейтса делает свое дело. У меня такое ощущение, что он будет использоваться здесь довольно часто, поскольку его легко и быстро реализовать. Здесь есть какая-то петля / задание, но, честно говоря , в гольф не так уж много; это просто короткий от природы.

void t(int[]s){for(int i=s.length,t,x;i>0;t=s[x*=Math.random()],s[x]=s[i],s[i]=t)x=i--;}

С некоторыми переносами строк:

void t(int[]s){
    for(int i=s.length,t,x;
        i>0;
        t=s[x*=Math.random()],
        s[x]=s[i],
        s[i]=t
    )
        x=i--;
}

Это перемешивает на месте, изменяя исходный массив s[]. Тестовая программа:

public class Shuffle {
    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9};
        new Shuffle().t(a);
        for(int b:a)
            System.out.print(b+" ");
    }
    void t(int[]s){for(int i=s.length,t,x;i>0;t=s[x*=Math.random()],s[x]=s[i],s[i]=t)x=i--;}
}
Geobits
источник
1
Нет, в заявке говорится, что вы можете предположить, что она « абсолютно однородна в требуемом диапазоне ». Запрошенный диапазон Math.random()имеет размер, который является степенью двойки, так что это не соответствует спецификации.
Питер Тейлор
1
@PeterTaylor Ян и Джобитс действительно интерпретируют то, как я задумал правило - что вам не нужно беспокоиться о фактической длине цикла вашего PRNG.
Мартин Эндер
1
@ MartinBüttner, длина цикла здесь не является проблемой - она ​​покрывается вашим правилом. Грубость поплавков есть.
Джон Дворжак
3
@TheBestOne Это на один байт короче, чем единственное в настоящее время опубликованное решение Python;)
Geobits
1
Уже нет! : D
Sp3000
8

Python 2, 86 байт

from random import*
def S(L):i=len(L);exec"i-=1;j=randint(0,i);L[i],L[j]=L[j],L[i];"*i

Это функция, которая перемешивает массив на месте, не возвращая его, используя простую реализацию перемешивания Фишера-Йейтса . Получение случайных чисел из Python стоит дорого ...

Спасибо @xnor и @colevk за советы.

Sp3000
источник
Это выражение диапазона выглядит довольно громоздким. Конечно, короче отсчитывать вручную как while i:i-=1;...?
xnor
@xnor Да, это так - спасибо за это. Я постоянно забываю, что, whileкак правило, короче, чем forдля такого рода вещи ...
Sp3000
1
Ой ... теперь мой ответ на Java не превосходит это. Я был очень счастлив за очень короткое время :(
Geobits
Вы можете сохранить еще 2 байта, сделав i=len(L)и поместив декремент в начало цикла while.
colevk
8

J, 45 44 символа

Это было сложно.

<@({.,?@#@}.({,<^:3@[{])}.)&>/@(<"0@i.@#,<)

Вот объяснение:

  1. # y: Подсчет из y, то есть, количество элементов в y.
  2. ?@# y: Случайное число, равномерно распределенное по диапазону от 1до (#y)-1.
  3. x { y: Элемент из y индекса x.
  4. (<<<x) { y: Все элементы, кроме элемента с индексом xв y.
  5. x , y: y Добавляется к x.
  6. x ({ , <^:3@[ { ]) y: Элемент с индексом xв y, то все остальные элементы.
  7. (?@# ({ , <^:3@[ { ]) ]) yСлучайно y, потом все остальные предметы.
  8. x {. y: Первые xпредметы взяты из y.
  9. x }. y: Первые xпредметы выпали из y.
  10. x ({. , }.) y: Первые xпредметы взяты из y, затем первые xпредметы выброшены изy
  11. x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y: Первые xэлементы, взятые из y, затем первые xэлементы из yобработанных, как в номере 7.
  12. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) yТо же самое с выпавшим дропом, чтобы спасти одного персонажа.
  13. u/ y: u вставлено между элементами y.
  14. < y: в y штучной упаковке .
  15. <"0 yКаждый предмет в y штучной упаковке .
  16. i. y: целые числа от 0до y - 1.
  17. i.@# y: целые числа от 0до (#y) - 1.
  18. (<"0@i.@# , <) y: Целые из 0к (#y) - 1каждой коробке , а затем yв одном окне. Это необходимо, потому что массивы в J одинаковы. Коробка скрывает форму своего содержимого.
  19. x u&v y: Как (v x) u (v y).
  20. > y: y открыл , то есть без своей коробки.
  21. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y фраза из числа 12 применяется к ее без коробки аргументы.
  22. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ yфраза из числа 21 вставлена между пунктами y.
  23. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) yФраза из числа 22 применяется к результату фразы из числа 18 или равномерной перестановки предметов y.
FUZxxl
источник
1
Я просто не могу различить все скобки. И этот тройной бокс <@<@<@[тоже загадка ... В ожидании объяснения. :)
randomra
2
Как только это будет объяснено, я мог бы гораздо больше шансов поднять этот ответ ;-)
Джон Дворжак
@randomra Здесь вы идете.
FUZxxl
@JanDvorak Удовлетворительное объяснение?
FUZxxl
Отличное объяснение! Я не знал обо всем использовании в штучной упаковке from( {). И мне действительно нравится &>/трюк, чтобы манипулировать списком. Я уверен, что мог бы использовать это пару раз раньше.
Рандомра
5

Pyth, 25 байт

Проверьте это здесь.

Еще одна реализация Фишера-Йейтса. По сути, это то же самое, что и решение @ Sp3000 python, только в pyth.

FNrlQ1KONJ@QN XXQN@QKKJ)Q

Спасибо @Jakube за трюк с обменом

<implicit>    Q=input()
FNrlQ1        For N in len(Q) to 1, only goes len Q-1 because how range implemented in pyth
 KON          K = random int 0-N
 J@QN         J=Q[N]
 <space>      Suppress print
 XXQN@QKKJ    Swap K and J
)             End for
Q             Print Q
Maltysen
источник
Вы можете сохранить два байта, комбинируя эти два назначения списка: `XXQN @ QKKJ` вместо` XQN @ QK XQKJ`.
января
@Jakube спасибо за совет. Я знал, что должен быть способ поменять значения в списке, и это действительно умно. Вы должны добавить его в список советов.
Maltysen
4

Perl, 68 56 44

Как и во многих других решениях, здесь используется алгоритм Фишера-Йейтса .

С помощью комментария Nutki , 12 символов сохраняются при использовании $_вместо $iи выполнении операций с индексами массива.

44:

sub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}

56:

sub f{$i=@_;$j=int(rand$i),@_[$i,$j]=@_[$j,$i]while$i--}

Это мой первый Codegolf.

Bonsaigin
источник
Неплохое начало, я не знал, что вы можете использовать в @_[...]качестве rvalue, как это. Может быть в гольф дальше sub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}.
Nutki
3

C 63 61 60 байт

i,t;s(a,m)int*a;{for(;m;a[m]=t)t=a[i=rand()%m--],a[i]=a[m];}

Просто прямая реализация Фишера-Йейтса, которая сортирует данный массив на месте. Прекрасно компилируется и связывается с компилятором visual studio (vs2013, другие версии не тестировались) и компилятором Intel. Приятно выглядящая функция подписи есть s(int array[], int length). Я законно впечатлен, я победил Python и Ruby.

Это предполагает, что srand()вызывается, и rand () реализован правильно, но я считаю, что это правило учитывает это:

You may assume that any built-in random number method runs in O(1) and is perfectly uniform over the requested interval

Красиво отформатированная версия:

index, temp;
shuffle(array, length) int* array;  {
    for(;length; array[index] = temp)
        index = rand() % length--,
        temp = array[length],
        array[length] = array[index];
}
pseudonym117
источник
Я думаю, что достаточно сделать заголовок функции s(a,m)*a{, но я не уверен и тоже не хочу тестировать. Вы можете сделать- xorswap, как в a[i]^=a[m]^=a[i]^=a[m]. Это также позволяет избежать необходимости декларировать t.
FUZxxl
@FUZxxl Я полагаю, что своп xor вызывает проблемы, если i==m.
Geobits
@ Geobits действительно. Я упустил эту возможность.
FUZxxl
Я просто пытался понять, почему это не сработало ... я должен был это запомнить. Также мне нужно s(a,m)int*aдля Visual Studio и компилятор Intel. У меня не установлены gcc или clang для тестирования, но я предполагаю, что они тоже будут жаловаться.
псевдоним117
Это довольно впечатляюще. Попробовав множество модификаций, которые ничего не спасли, мне удалось найти способ сохранить 2 символа. Если вы измените порядок обмена так, чтобы он стал первым оператором обмена t=a[i], вы можете переместить i=rand()%m--оператор внутрь как индекс массива.
Runer112
3

Октава, 88 77 байт

function s=r(s)for(i=length(s):-1:1)t=s(x=randi(i));s(x)=s(i);s(i)=t;end;end

Еще одна реализация Фишера-Йейтса ... Должна быть довольно простой, если я добавлю обычные возвраты строк и интервал:

function s=r(s)
  for(i=length(s):-1:1) # Counting down from i to 1
    t=s(x=randi(i));    # randi is builtin number generator for an int from 0 to i
    s(x)=s(i);
    s(i)=t;
  end
end

К сожалению, «конечные» ключевые слова действительно убивают счет в гольфе. Эй, я могу использовать «конец» вместо «endfor» и «endfunction»!

dcsohl
источник
1
Просто FYI, что «байт» на самом деле не требует кода, он просто делает уверен , что это заголовок, который содержит запятую (отделить язык) и , по меньшей мере , одно число после запятой, а затем просто выбирает последний число, которое не вычеркнуто. Иметь «байты» там все же приятно. ;)
Мартин Эндер
1
Вы можете сохранить 1 байт, используя numelвместо lenght. В качестве бонуса ваша программа также будет работать с двумерными массивами или матрицами;)
paul.oderso
2

Ява 8, 77

(x)->{for(int i=x.length,j,t;;t=x[j*=Math.random()],x[j]=x[i],x[i]=t)j=i--;};

Это лямбда, принимающая int[]и возвращающая пустоту. Моя первая попытка показалась мне не очень интересной, поэтому я решил сделать так, чтобы она была исключена.

Тестовая программа:

interface shuff {
    void shuff(int[] x);
}
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        shuff s = (x)->{for(int i=x.length,j,t;;t=x[j*=Math.random()],x[j]=x[i],x[i]=t)j=i--;};
        int[] x = {3, 9, 2, 93, 32, 39, 4, 5, 5, 5, 6, 0};
        try {
            s.shuff(x);
        } catch(ArrayIndexOutOfBoundsException _) {}
        for(int a:x) System.out.println(a);
    }
}
feersum
источник
1
Разве не обманывает использование лямбды, чтобы обойти необходимость написания сигнатуры функции, когда вам нужно предоставить делегат, чтобы использовать лямбду где угодно? Кроме того ... ты не можешь бросить скобки вокруг Math.random()?
Роулинг
1
@Rawling Вы можете проголосовать в этом мета-вопросе . В настоящее время за лямбды проголосовало 9, а против - 0. Да, скобки могут быть удалены.
feersum
Да, если есть мета-пост и пока что единодушное мнение, то увольняйте. (И наслаждайся двумя-более низкими показателями по гольфу на мне: p)
Роулинг
3
Я думаю, что в нормальном случае несправедливо останавливать функцию по исключению, не так ли?
Qwertiy
1
@Qwertiy Каждому свое ... Вы думаете, это несправедливо, я думаю, что это здорово.
feersum
2

Golflua, 37

Как запустить Golflua?

~@i=1,#X`r=M.r(i)X[i],X[r]=X[r],X[i]$

Входные данные предоставляются в виде таблицы в переменной X. Таблица перемешивается на месте.

Пример использования:

> X={0,-45,8,11,2}
> ~@i=1,#X`r=M.r(i)X[i],X[r]=X[r],X[i]$
> w(T.u(X))
-45 0 8 11 2
МНИИП
источник
2

R, 79 байт

f=function(x){n=length(x);for(i in 1:n){j=sample(i:n,1);x[c(i,j)]=x[c(j,i)]};x}

Это простая реализация шаффла Фишера-Йейтса. Функция R sampleрисует простую случайную выборку заданного размера из заданного вектора с равной вероятностью. Здесь мы рисуем случайную выборку размером 1 на каждой итерации из целых чисел i, ..., n. Как указано в вопросе, это можно предположить как O (1), поэтому во всей этой реализации должно быть O (N).

Алекс А.
источник
2

Матлаб, 67

Также реализует Фишер-Йейтс.

a=input('');n=numel(a);for i=1:n;k=randi(i);a([i,k])=a([k,i]);end;a

Я думал, что это слишком плохо, я не мог использовать randpermфункцию Matlab . Но после некоторого возни, я подумал, что могу посмотреть на источник, randpermчтобы увидеть, как это делается, и я был удивлен, увидев, что была только одна строка: [~,p] = sort(rand(1,n))=)

flawr
источник
2

Perl, 44

sub f{($_[$x],$_)=($_,$_[$x=rand++$i])for@_}

Еще один Perl в 44 символов. Пример использования:

@x=(1..9);f(@x);print@x
nutki
источник
2

Mathematica, 82 90 83 93 байта

Примечание. Эта вариация тасования Фишера-Йейтса на самом деле является решением Мартина Бюттнера, с некоторой обработкой кода алефальфой. sэто входной массив. Ничего особенного, но иногда простые вещи самые неуловимые.

f@s_:=(a=s;m=Length@a;Do[t=a[[r=RandomInteger@{1,m-1}]];a[[r]]=a[[m]]; a[[m]]=t,{n,1,m-1}];a)
DavidC
источник
Вы можете использовать Doздесь. Это короче While.
алефальфа
2

Рубин, 57 байт

->a{a.size.times{|i|j=rand(i+1);a[i],a[j]=a[j],a[i]};p a}

Вход (как лямбда-функция):

f.([1,2,3,4,5])

Выход:

[2, 1, 4, 3, 5]
Нулевое волокно
источник
2

К, 31 символ

f:{{l[i:x,1?x]:l@|i}'|!#l::x;l}

Не такой короткий, как тот, который я выложил раньше (который был дисквалифицирован) ... о, хорошо.

Это основной случай Фишера-Йейтса. Это было построено с большой помощью из списка рассылки Kona .

kirbyfan64sos
источник
2

JavaScript (ES6), 66

Эта функция перемешивает массив на месте. Он также возвращает массив побочных продуктов, который НЕ является перемешанным выводом и не должен рассматриваться.

F=a=>a.map((v,i)=>a[a[i]=a[j=0|i+Math.random()*(a.length-i)],j]=v)
edc65
источник
2

MATL , 16 байт

XH`HnYr&)XHxvHHn

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

Фишер-Йейтс в МАТЛ. Почти треть этой программы посвящена письмуH , которая соответствует функции буфера обмена в MATL.

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

Sanchises
источник
2

Джапт, 12

rÈiMqZÄ Y}[]

Попытайся!

-10 (около половины;) благодаря @Shaggy!

Я давно хотел попробовать язык игры в гольф, и у переводчика Japt была хорошая документация и возможность опробовать вещи в браузере.

Ниже приведена стратегия, которую я выбрал:

  • Уменьшите входное заполнение пустым массивом
  • На каждом шаге найдите случайный слот для вставки текущего элемента
Dana
источник
1
Добро пожаловать в Japt, рад, что вы с нами. Я думаю, что это работает для 9 байтов, используя тот же метод. Если ГСЧ не является удовлетворительным, попробуйте это вместо этого.
лохматый
@ Shaggy - Спасибо за советы! :) В итоге я использовал слегка модифицированную версию вашего второго решения. Поскольку 3-й параметр функции Reduce является индексом, мы уже знаем длину.
Дана
1

Javascript ES6, 69

a=>{m=a.length;while(m)[a[m],a[i]]=[a[i=~~(Math.random()*m--)],a[m]]}

Это Фишер-Йейтс.

PS: можно протестировать в Firefox

Qwertiy
источник
@ MartinBüttner, удалил его :)
Qwertiy
1

Хаскелл, 170

import System.Random
import Data.Array.IO
s a=do(_,n)<-getBounds a;sequence$map(\i->do j<-randomRIO(i,n);p<-a%i;q<-a%j;writeArray a j p;return q)[1..n]where(%)=readArray

Другое решение Фишера-Йейтса, вдохновленное алгоритмом по адресу https://wiki.haskell.org/Random_shuffle .

s это функция, которая имеет подпись: IOArray Int a -> IO [a]

Jmac
источник
1

CJam - 30

q~_,,W%{_I=I)mr:J2$=@I@tJ@t}fI

Попробуйте это в http://cjam.aditsu.net/

Пример ввода: [10 20 30 40 50]
Пример вывода: 3020401050(добавитьp в конце кода для красивой печати)

Если коду разрешено принимать входные данные из стека (например, функции), то первые 2 символа можно удалить, уменьшив размер до 28.

Объяснение:

Код длиннее, чем я ожидал, из-за отсутствия оператора «swap» для массивов
(будет реализовано позже: p)

q~            read and evaluate the input (let's call the array "A")
_,,           make an array [0 1 2 ... N-1] where N is the size of A
W%            reverse the array, obtaining [N-1 ... 2 1 0]
{…}fI         for I in this array
    _I=       push A[I]
    I)mr:J    push a random number from 0 to I (inclusive) and store it in J
              stack: A, A[I], J
    2$=       get A[J]
    @I@t      set A[I] = A[J]
              stack: former A[I], A
    J@t       set A[J] = former A[I]
aditsu
источник
Как уже упоминалось в комментариях, я боюсь, что это недействительно. По крайней мере _, O (N) (внутри петли O (N)). К сожалению, я не вижу способа обойти это в CJam.
Мартин Эндер
Списки обрабатываются как неизменяемые объекты, поэтому дублирование просто реализуется как дублирование ссылки. Это на самом деле, tчто убивает его, так как он не может изменить список и теперь должен создать копию.
Runer112
@ MartinBüttner Я собирался опубликовать то же самое, что и Runer112; да, может быть проблема с t, я хотел бы улучшить ее в будущих версиях ..
aditsu
Таким образом, этот код соответствует духу вопроса, но не «букве», из-за проблем с реализацией на внутреннем языке.
aditsu
1

JavaScript (ES 6), 61

S=a=>(a.map((c,i)=>(a[i]=a[j=Math.random()*++i|0],a[j]=c)),a)

Вы можете проверить это здесь , просто добавив строку с надписью shuffle = S(только Firefox).

core1024
источник
1

СТАТА, 161

di _r(s)
set ob wordcount($s)
token $s
g a=0
foreach x in $s{
gl j=floor(runiform()*_n)+1
replace a=`$j' if word($s,_n)=`x'
replace a=`x' if word($s,_n)=`$j'
}
l

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

bmarks
источник
Что _nв этом?
Мартин Эндер
_n - номер текущего наблюдения.
отмечается
1

Java, 93 байта

a->{for(int b=0,c,d=0,e=a.length;b<e;c=a[b],a[b]=a[d],a[d]=c,b++,d=b)d+=Math.random()*(e-b);}

Пример использования: http://ideone.com/RqSMnZ

Номер один
источник
1

SQF, 91 байт

params["i"];{n=floor random count i;i set[_forEachIndex,i select n];i set[n,_x]}forEach i;i
Οurous
источник
1
Это предвзято (см. «Swap (i <-> random)» в Will It Shuffle), но вы можете превратить его в Fisher-Yates (который беспристрастен), заменив %xна %i.
Мартин Эндер