Sobre a série

Estarei executando uma pequena série de desafios de código-golfe que giram em torno do tema da aleatoriedade. Basicamente, este será um campo de golfe de 9 buracos , mas está espalhado por várias perguntas. Você pode participar de qualquer desafio individualmente, como se fosse uma pergunta normal.

No entanto, manterei uma tabela de líderes em todos os desafios. A série terá 9 desafios (por enquanto), um publicado a cada poucos dias. Todo usuário que participa dos nove desafios é elegível para ganhar a série inteira. A pontuação geral deles é a soma dos envios mais curtos em cada desafio (portanto, se você responder a um desafio duas vezes, apenas a melhor resposta será contada na pontuação). Se alguém ocupar o primeiro lugar nesta classificação geral por 28 dias , concederei a eles uma recompensa de 500 representantes .

Embora eu tenha várias idéias alinhadas para a série, os desafios futuros ainda não estão definidos. Se você tiver alguma sugestão, informe-me na postagem da sandbox relevante .

Buraco 1: embaralhar uma matriz

A primeira tarefa é bem simples: dada uma matriz não vazia de números inteiros, embaralhe-a aleatoriamente. Existem algumas regras, porém:

• Toda permutação possível deve ser retornada com a mesma probabilidade (para que o shuffle tenha uma distribuição uniforme). Você pode verificar se o seu algoritmo é uniforme / imparcial implementando-o em JavaScript no Will it Shuffle , que produzirá uma matriz de vieses - o resultado deve parecer tão uniforme quanto seus Fisher-Yates internos ou classificação (ordem aleatória) .
• Você não deve usar nenhum método interno ou de terceiros para embaralhar a matriz ou gerar uma permutação aleatória (ou enumerar todas as permutações). Em particular, a única função aleatória interna que você pode usar é obter um único número aleatório de cada vez . Você pode assumir que qualquer método de número aleatório interno é executado em O (1) e é perfeitamente uniforme durante o intervalo solicitado (em um sentido matemático - você pode ignorar detalhes da representação em ponto flutuante aqui). Se o seu idioma permitir que você obtenha uma lista de m números aleatórios de uma só vez, você poderá usar este recurso, desde que os números m sejam independentes um do outro e contados como O (m).
• Sua implementação não deve exceder uma complexidade de tempo de O (N) , em que N é o tamanho da matriz a ser embaralhada. Por exemplo, você não pode "classificar por números aleatórios".
• Você pode embaralhar a matriz no lugar ou criar uma nova matriz (nesse caso, a matriz antiga pode ser modificada da maneira que desejar).

Você pode escrever um programa completo ou uma função e receber entradas via STDIN, argumento de linha de comando, argumento de função ou prompt e produzir saída via valor de retorno ou imprimindo em STDOUT (ou alternativa mais próxima). Se você escrever uma função que embaralhe a matriz no lugar, não precisará retorná-la, é claro (desde que o seu idioma permita acessar a matriz modificada após o retorno da função).

A entrada e a saída podem estar em qualquer formato conveniente de lista ou sequência, mas devem suportar números inteiros arbitrários no intervalo -2 ³¹ ≤ x <2 ³¹ . Em princípio, seu código deve funcionar com matrizes de comprimento 2 a ³¹ , embora isso não precise necessariamente caber em sua memória ou ser concluído dentro de um período de tempo razoável. (Eu só não quero ver limites arbitrários de tamanho para loops de código rígido ou algo assim.)

Isso é código de golfe, então a submissão mais curta (em bytes) vence.

Entre os melhores

O trecho a seguir gerará uma tabela de classificação em todos os desafios da série.

Para garantir que suas respostas sejam exibidas, inicie todas as respostas com um título, usando o seguinte modelo de remarcação:

# Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

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

(O idioma não é mostrado no momento, mas o snippet exige e o analisa, e eu posso adicionar um cabeçalho por idioma no futuro.)

/* Configuration */

var QUESTION_IDs = [45302, 45447, 46991, 49394, 51222, 66319, 89621, 120472]; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!.FjwQBrX2KXuFkv6p2lChi_RjzM19";

/* App */

var answers = [], page = 1, currentQ = -1;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_IDs.join(";") + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}


function getAnswers() {
  $.ajax({
    url: answersUrl(page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      if (data.has_more) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SIZE_REG = /\d+(?=[^\d&]*(?:<(?:s>((?!>).)*<\/s>|((?!>).)+>)[^\d&]*)*$)/;
var NUMBER_REG = /\d+/;
var LANGUAGE_REG = /^#*\s*([^\n,]+)(?=,)/;//

function shouldHaveHeading(a) {
  var pass = false;
  var lines = a.body_markdown.split("\n");
  try {
    pass |= /^#/.test(a.body_markdown);
    pass |= ["-", "="]
              .indexOf(lines[1][0]) > -1;
    pass &= LANGUAGE_REG.test(a.body_markdown);
  } catch (ex) {}
  return pass;
}

function shouldHaveScore(a) {
  var pass = false;
  try {
    pass |= SIZE_REG.test(a.body_markdown.split("\n")[0]);
  } catch (ex) {}
  if (!pass) console.log(a);
  return pass;
}

function getAuthorName(a) {
  return a.owner.display_name;
}

function getAuthorId(a) {
  return a.owner.user_id;
}

function process() {
  answers = answers.filter(shouldHaveScore)
                   .filter(shouldHaveHeading);
  answers.sort(function (a, b) {
    var aB = +(a.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0],
        bB = +(b.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0];
    return aB - bB
  });

  var users = {};
  answers.forEach(function (a) {
    var headline = a.body_markdown.split("\n")[0];
    var question = QUESTION_IDs.indexOf(a.question_id);
    var size = parseInt((headline.match(SIZE_REG)||[0])[0]);
    var language = headline.match(LANGUAGE_REG)[1];
    var user = getAuthorName(a);
    var userId = getAuthorId(a);
    if (!users[userId]) users[userId] = {name: user, nAnswer: 0, answers: []};
    if (!users[userId].answers[question]) {
      users[userId].answers[question] = {size: Infinity};
      users[userId].nAnswer++;
    }
    if (users[userId].answers[question].size > size) {
      users[userId].answers[question] = {size: size, link: a.share_link}
    }
  });
  
  
  var sortedUsers = [];
  for (var userId in users)
    if (users.hasOwnProperty(userId)) {
      var user = users[userId];
      user.score = 0;
      user.completedAll = true;
      for (var i = 0; i < QUESTION_IDs.length; ++i) {
        if (user.answers[i])
          user.score += user.answers[i].size;
        else
          user.completedAll = false;
      }
      sortedUsers.push(user);
    }  
  
  sortedUsers.sort(function (a, b) {
    if (a.nAnswer > b.nAnswer) return -1;
    if (b.nAnswer > a.nAnswer) return 1;
    return a.score - b.score;
  });
  
  var place = 1;
  for (var i = 0; i < sortedUsers.length; ++i) {
    var user = sortedUsers[i];
    var row = '<tr><td>'+ place++ +'.</td><td>'+user.name+'</td>';
    for (var j = 0; j < QUESTION_IDs.length; ++j) {
      var answer = user.answers[j];
      if (answer)
        row += '<td><a href="'+answer.link+'">'+answer.size+'</a></td>';
      else
        row += '<td class="missing"></td>';
    }
    row += '<td></td>';
    if (user.completedAll)
      row += '<td class="total">'+user.score+'</td>';
    else
      row += '<td class="total missing">'+user.score+'</td>';
    row += '</tr>';
    $("#users").append(row);
  }
}

body { text-align: left !important}

#leaderboard {
  width: 500px; 
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

td.total {
  font-weight: bold;
  text-align: right;
}

td.missing {
  background: #bbbbbb;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="leaderboard">
  <h2>Leaderboard</h2>
  <p>
    Missing scores are shown as grey cells. A grey total indicates that the user has not participated in all challenges and is not eligible for the overall victory yet.
  </p>
  <table class="_user-list">
    <thead>
      <tr><td></td><td>User</td>
        <td><a href="https://codegolf.stackexchange.com/q/45302/8478">#1</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/45447/8478">#2</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/46991/8478">#3</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/49394/8478">#4</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/51222/8478">#5</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/66319/8478">#6</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/89621/8478">#7</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/120472/8478">#8</a></td>
        <td></td><td>Total</td>
      </tr>
    </thead>
    <tbody id="users">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

Dyalog APL, 25 24 bytes

Primeiro para a solução de 25 caracteres: 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[⍵]

Após algumas transformações de equivalência acima:

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

podemos nos livrar da tarefa i←e salvar um personagem:

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

Código de máquina 80386, 44 24 bytes

Hexdump do código:

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

Agradecimentos a FUZxxl, que sugeriu o uso da rdrandinstrução.

Aqui está o código fonte (pode ser compilado pelo 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;
    }
}

Mais uma implementação de Fisher-Yates. A maior parte do golfe foi alcançada através da passagem de parâmetros nos registros.

Java, 88 101

Um embaralhamento básico de Fisher-Yates faz o truque. Sinto que ele será usado com bastante frequência aqui, pois é rápido e fácil de implementar. Há alguns loops / tarefas aqui, mas honestamente não há muito para jogar golfe; é apenas curto por natureza.

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

Com algumas quebras de linha:

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

Isso muda de lugar, modificando a matriz original s[]. Programa de teste:

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

Python 2, 86 bytes

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

Essa é uma função que embaralha a matriz no lugar sem retorná-la, usando uma implementação direta do embaralhamento Fisher-Yates . Obter números aleatórios do Python é caro ...

Obrigado a @xnor e @colevk por dicas.

J, 45 44 caracteres

Este foi um assunto complicado.

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

Aqui está uma explicação:

1. # y: A contagem de y, isto é, o número de elementos emy .
2. ?@# y: Um número aleatório distribuído uniformemente no intervalo de 1até(#y)-1 .
3. x { y: O item de y no índice x.
4. (<<<x) { y: Todos os itens, exceto o item no índice xem y.
5. x , y: y anexado a x.
6. x ({ , <^:3@[ { ]) yO item no índice xem y, em seguida, todos os outros itens.
7. (?@# ({ , <^:3@[ { ]) ]) yUm aleatório y, e todos os outros itens.
8. x {. y: Os primeiros xitens tomadas a partir y.
9. x }. y: Os primeiros xitens caiu dey .
10. x ({. , }.) y: Os primeiros xitens tomadas a partir y, então os primeiros xitens caiu dey
11. x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y: Os primeiros xitens tomadas a partir y, então a primeira xitens dey processados tal como no número 7.
12. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y: A mesma coisa com a gota puxada para salvar um personagem.
13. u/ y: u inserido entre os itens de y.
14. < y: em y caixa .
15. <"0 y: Cada item da y caixa .
16. i. y: números inteiros de 0até y - 1.
17. i.@# y: números inteiros de 0até (#y) - 1.
18. (<"0@i.@# , <) y: Números inteiros de 0para (#y) - 1cada caixa e, yem seguida, em uma única caixa. Isso é necessário porque matrizes em J são uniformes. Uma caixa oculta a forma do seu conteúdo.
19. x u&v y: como (v x) u (v y).
20. > y: y aberto , ou seja, sem sua caixa.
21. x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y a frase do número 12 se aplica a seus argumentos sem caixa.
22. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ ya frase do número 21 inserida entre os itens de y.
23. ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) ya frase do número 22 aplicada ao resultado da frase do número 18 ou uma permutação uniforme dos itens de y.

Pitão, 25 bytes

Teste aqui.

Mais uma implementação de Fisher-Yates. É essencialmente o mesmo que a solução python @ Sp3000, apenas em pyth.

FNrlQ1KONJ@QN XXQN@QKKJ)Q

Obrigado a @Jakube pelo truque de troca

<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

Perl, 68 56 44

Como muitas outras soluções, isso usa o Fisher-Yates algoritmo .

Usando o comentário de nutki , 12 caracteres são salvos usando em $_vez de $ie executando as operações nos índices da matriz.

44:

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

56:

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

Este é o meu primeiro codegolf.

C, 63 61 60 bytes

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

Apenas uma implementação direta do Fischer-Yates que classifica a matriz fornecida no local. Compila e vincula perfeitamente com o compilador visual studio (vs2013, não testou as outras versões) e o compilador Intel. A assinatura da função de aparência agradável és(int array[], int length) . Estou legitimamente impressionado por vencer o Python e o Ruby.

Isso assume que srand()é chamado e rand () é implementado corretamente, mas acredito que esta regra permite isso:

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

Versão bem formatada:

index, temp;
shuffle(array, length) int* array;  {
    for(;length; array[index] = temp)
        index = rand() % length--,
        temp = array[length],
        array[length] = array[index];
}

Oitava, 88 77 bytes

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

Ainda outra implementação de Fisher-Yates ... Deveria ser bastante direta se eu adicionar os retornos e espaçamentos usuais da linha:

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

As palavras-chave "final" realmente matam a pontuação de golfe aqui, infelizmente. Ei, eu posso usar "end" em vez de "endfor" e "endfunction"!

Java 8, 77

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

É uma lambda tomando int[] e retornando vazio. Minha primeira tentativa não pareceu muito interessante, então decidi sair lançando uma exceção.

Programa de teste:

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

Golflua, 37

Como executar o Golflua?

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

A entrada é fornecida como uma tabela na variável X. A tabela é embaralhada no lugar.

Exemplo de uso:

> 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

R, 79 bytes

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}

Esta é uma implementação direta do shuffle de Fisher-Yates. A função R sampledesenha uma amostra aleatória simples de um determinado tamanho de um determinado vetor com igual probabilidade. Aqui estamos desenhando uma amostra aleatória do tamanho 1 em cada iteração a partir dos números inteiros i, ..., n. Como afirmado na pergunta, isso pode ser assumido como O (1); portanto, em toda essa implementação deve ser O (N).

Matlab, 67

Também implementando Fisher-Yates.

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

Achei muito ruim não poder usar a randpermfunção do Matlab . Mas, depois de algumas brincadeiras, pensei em ver a fonte randpermpara ver como isso é feito, e fiquei surpreso ao ver que havia apenas uma linha: [~,p] = sort(rand(1,n))=)

Perl, 44

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

Outro perl em 44 caracteres. Exemplo de uso:

@x=(1..9);f(@x);print@x

Mathematica, 82 90 83 93 bytes

Nota: Essa variação do embaralhamento de Fisher-Yates é na verdade a solução de Martin Büttner, com algum código aparecendo por alefalpha. sé a matriz de entrada. Nada de sofisticação, mas às vezes as coisas simples são as mais esquivas.

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)

Ruby, 57 bytes

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

Entrada (como função lambda):

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

Saída:

[2, 1, 4, 3, 5]

TI-BASIC, 46 bytes

For(X,dim(L1),2,-1:randInt(1,X→Y:L1(X→Z:L1(Y→L1(X:Z→L1(Y:L1

1   111   2  1111112       1111112 111112 1112 111112 1112

Origem para contagem de bytes

K, 31 caracteres

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

Não é tão curto quanto o que eu coloquei antes (que foi desclassificado) ... tudo bem.

É um embaralhamento básico de Fisher-Yates. Isso foi construído com muita ajuda da lista de discussão Kona .

JavaScript (ES6), 66

Essa função embaralha a matriz no lugar. Ele também retorna uma matriz de subprodutos que NÃO é a saída aleatória e não deve ser considerada.

F=a=>a.map((v,i)=>a[a[i]=a[j=0|i+Math.random()*(a.length-i)],j]=v)

MATL , 16 bytes

XH`HnYr&)XHxvHHn

Experimente online!

Fisher-Yates em MATL. Quase um terço deste programa é dedicado à letra H, que corresponde à função da área de transferência no MATL.

Basicamente, Harmazena os itens não utilizados da entrada, enquanto a pilha controla a lista aleatória.

Japt, 12

rÈiMqZÄ Y}[]

Tente!

-10 (cerca de metade;) graças a @Shaggy!

Eu estava querendo experimentar uma linguagem de golfe, e o intérprete Japt tinha boa documentação e uma maneira de experimentar as coisas no navegador.

Abaixo está a estratégia que tomei:

• Reduza a propagação de entrada com uma matriz vazia
• Em cada etapa, encontre um slot aleatório para inserir o elemento atual

Javascript ES6, 69

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

É o Fisher-Yates.

PS: Pode ser testado no Firefox

Pitão, 27 bytes

Teste aqui

FkQJOhlYaY?@YtJJkIJ XYtJk;Y

Esta é uma implementação do shuffle incremental de Fisher-Yates, mencionado em segundo lugar aqui .

Haskell, 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

Outra solução Fisher-Yates inspirada no algoritmo em https://wiki.haskell.org/Random_shuffle .

s é uma função que possui assinatura: IOArray Int a -> IO [a]

CJam - 30

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

Experimente em http://cjam.aditsu.net/

Exemplo de entrada: [10 20 30 40 50]
Exemplo de saída: 3020401050(adicione a pno final do código para obter uma impressão bonita)

Se o código puder receber a entrada da pilha (como uma função), os 2 primeiros caracteres poderão ser removidos, reduzindo o tamanho para 28.

Explicação:

O código é mais longo do que eu esperava, devido à falta de um operador "swap" para matrizes
(a ser implementado posteriormente: 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]

JavaScript (ES 6), 61

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

Você pode testá-lo aqui , apenas adicionando uma linha que diz shuffle = S(apenas Firefox).

STATA, 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

Espera entrada como números separados por espaço. Posso remover os cabeçalhos e os números de observação da saída, se você quiser, mas, caso contrário, isso é mais curto.

Java, 93 bytes

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

Exemplo de uso: http://ideone.com/RqSMnZ

SQF, 91 bytes

params["i"];{n=floor random count i;i set[_forEachIndex,i select n];i set[n,_x]}forEach i;i

Perl, 41 bytes

sub f{push@b,splice@_,rand@_,1while@_;@b}

Experimente online!